3. 设计

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 1000 + 10;
 5 struct node {
 6     int start;
 7     int end;
 8     int id;
 9 }a[maxn];  //结构体用来记录该项活动的开始时间，截止时间，编号 
10 bool cmp(struct node& a, struct node& b) {
11     return a.end < b.end;
12 }
13 int n, now = 0;      //now用来记录当前活动结束的时间 
14 int cnt = 0;        //cnt用来记录不相容的活动的个数 
15 int ans[maxn];    //记录不相容的活动的编号 
16 int main() {
17     scanf("%d", &n);
18     for (int i = 1; i <= n; ++i) {
19         scanf("%d %d", &a[i].start, &a[i].end);
20         a[i].id = i;
21     }
22     sort(a + 1, a + 1 + n, cmp);         //按照截止时间从小到大排序 
23     for (int i = 1; i <= n; ++i) {
24         if (a[i].start >= now) {      //表明该活动可以被选择 
25             ans[++cnt] = a[i].id;
26             now = a[i].end;
27         }
28     }
29     sort(ans + 1, ans + 1 + cnt);
30     printf("%d
", cnt);
31     for (int i = 1; i <= cnt; ++i) {
32         if (i != 1)printf(" ");
33         printf("%d", ans[i]);
34     }
35 }

4. 分析

排序算法时间复杂度为：O(nlogn)

该贪心算法时间复杂度为：O(n)

5. 源码

https://github.com/JayShao-Xie/algorithm-work/blob/master/Greedy1.cpp