【问题描述】

小王要看电影，但是小王在m-n这段时间内很繁忙，无法看电影，但是小王今天心情非常好，能在任意没有事情的时间内看电影。

请帮帮小王安排时间，使得他能看到最多的电影。

【输入形式】

输入文件中包含多个测试数据。每个测试数据的第1行为一个正整数N(1<=N<=20)，表示电影院周六那天放映的电影数；然后是2行，第2行为N部电影各自的开始时间s，第3行为N部电影各自的结束时间t，0<=s

【输出形式】

对输入文件中的每个测试数据，输出小王最多能观看到的电影数。(忽略小王辗转放映厅的时间)

【样例输入】

8
0 1 4 7 9 10 13 12
7 4 9 13 15 13 19 15
5 10
0

【样例输出】

   3

【题目分析】

这是一道‘活动安排选择’的问题，用贪心算法，但是在贪心算法之前，要筛选，所有不与繁忙时间冲突的电影。

区间重合判断方法

若电影时间与繁忙时间不冲突，可以有：电影开始时间>=繁忙结束时间 || 电影结束时间<=繁忙开始时间

进而得到电影放映时间与繁忙时间冲突的条件 电影开始时间<繁忙结束时间 && 电影结束时间>繁忙开始时间

将所有的电影按照结束时间从小到大来排。

贪心步骤

先找到第一个的电影的开始时间，假设为第i个

然后循环从i+1开始，找到一场电影的开始时间与当前电影的结束时间不冲突的

然后当前电影切换为刚刚找到的电影，sum++。

贪心过程中，只讨论能看的电影，即不与繁忙时间冲突的电影。

代码如下

#include 
#include 
#include 
#include 
using namespace std;
struct film{int start;int end;
}set[30];
bool used[30] = { 0 };//记录哪些电影可以看，哪些不能看
int num;
int m;//繁忙开始时间
int n;//繁忙结束时间
int sum = 0;
int cmp(const void *a, const void *b) {return ((film *)a)->end - ((film *)b)->end;
}
void hoge() {int k = 99;int i = 2;for (i = 1; i <= num; i++) {if (used[i] == 1) {k = set[i].end;sum++;break;}}i++;for (; i <= num; i++) {if (used[i] == 1 && set[i].start >= k) {k = set[i].end;sum++;}}
}
void Rightful() {int i;for (i = 1; i <= num; i++) {if (m < set[i].end && n>set[i].start)used[i] = 0;}
}
int main() {//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);while (cin >> num) {sum = 0;if (num == 0)break;int i;for (i = 1; i <= num; i++) {cin >> set[i].start;used[i] = 1;//能看为1}for (i = 1; i <= num; i++)cin >> set[i].end;cin >> m >> n;qsort(set + 1, num, sizeof(set[1]), cmp);Rightful();//筛选不冲突的电影hoge();//贪心//pri();printf("%d\n", sum);}return 0;
}