时间限制：3000 ms | 内存限制：65535 KB
难度：4
- 描述
- 学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。
- 输入
- 第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。
随后的n行，每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间（Bi<=Ei) - 输出
- 对于每一组输入，输出最多能够安排的活动数量。
每组的输出占一行 - 样例输入
-
2
2
1 10
10 11
3
1 10
10 11
11 20 - 样例输出
-
1
2 - 提示
- 注意：如果上一个活动在t时间结束，下一个活动最早应该在t+1时间开始
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct act{
int s;
int e;
}STACT;
int compare(const void *a, const void *b){
STACT *acts1 = (STACT *)a;
STACT *acts2 = (STACT *)b;
return (acts1->e - acts2->e);
}
int main()
{
//m:num of test,n:num of activities
int m,n;
int i;
scanf("%d", &m);
getchar();
while (m--) {
scanf("%d", &n);
getchar();
STACT *ats=(STACT *)malloc(sizeof(STACT)*n);
memset(ats, 0x00, sizeof(STACT)*n);
for (i = ; i < n; ++i) {
scanf("%d%d", &ats[i].s, &ats[i].e);
}
qsort(ats, n, sizeof(ats[]), compare);
int sum=;
int curTime=-;
for (i = ; i < n; ++i) {
if(curTime < ats[i].s){
++sum;
curTime = ats[i].e;
}
else {
continue;
}
}
printf("%d\n", sum);
if(ats != NULL){
free(ats);
ats=NULL;
}
}
return ;
}
Time: 172ms Space:316
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct act{
int s;
int e;
}actnode[];
int compare(const void *a, const void *b){
act *acts1 = (act *)a;
act *acts2 = (act *)b;
return (acts1->e - acts2->e);
}
int main()
{
//m:num of test,n:num of activities
int m,n;
int i;
scanf("%d", &m);
getchar();
while (m--) {
scanf("%d", &n);
getchar(); memset(&actnode , 0x00, sizeof(actnode));
for (i = ; i < n; ++i) {
scanf("%d%d", &actnode[i].s, &actnode[i].e);
}
qsort(actnode, n, sizeof(actnode[]), compare);
int sum=;
int curTime=-;
for (i = ; i < n; ++i) {
if(curTime < actnode[i].s){
++sum;
curTime = actnode[i].e;
}
else {
continue;
}
}
printf("%d\n", sum); }
return ;
}
212ms 392
选择结束时间最早的,贪心算法
解体思路
有误:
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define debug(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl struct noac{
int Ti_s;
int Ti_e;
bool operator<(const noac& nc) const // DESC by Ti_s
{
return (Ti_s > nc.Ti_s);
}
friend void operator<<(ostream &os, const noac &nc)
{
os << nc.Ti_s << ' ' << nc.Ti_e << endl;
}
}tms[]; int main(){
int m,n;
scanf("%d", &m);
while (m--) {
scanf("%d", &n);
memset(&tms, , 0x00);
for (int i = ; i < n; ++i)
{
scanf("%d%d", &tms[i].Ti_s, &tms[i].Ti_e);
}
sort(tms, tms + n); int maxac = ;
for (int i = ; i < n; ++i)
{
int idx = i;
int sum = ;
for (int j = i+; j < n; ++j)
{
if(tms[idx].Ti_s >= tms[j].Ti_e)
{
++sum;
++idx;
}else
{
continue;
}
}
maxac = max(maxac, sum);
}
printf("%d\n", maxac);
}
return ;
}
比如说:
6
1 5
2 3
10 11
6 7
8 9
4 5
output: 4,而实际输出为5