题意:
给出一堆课,选课时间从s
i到e
i,每个学生可以从任意一个时刻开始选课,然后每隔5分钟选一次,如果在某个时刻t,存在某个课程i,s
i<t,e
i>t,那么可以选这门课。问最多可以选多少门课。
解法:
首先注意,选课时间是
开区间,(s,e),需要事先处理为
[s*2+1,e*2-1]然后就可以枚举起点然后贪心,每次取覆盖当前时间点的右端点最小的那个区间(课程)来选。
具体实现方法可以先按照s排序,然后建立一个以e为关键字的
小根堆,动态统计,这样复杂度O(nlogn)代码:
1 # include <cstdio>
2 # include <queue>
3 # include <algorithm>
4 # include <vector>
5 using namespace std;
6 int n;
7 const int N=305;
8 struct node
9 {
10 int s,e;
11 }data[N];
12 bool cmp(const node &a,const node &b)
13 {
14 return a.s<b.s;
15 }
16 struct cmp1
17 {
18 bool operator()(const node &a,const node &b) const
19 {
20 return a.e>b.e;
21 }
22 };
23 int main()
24 {
25 while(true)
26 {
27 scanf("%d",&n);
28 if(!n) break;
29 int start=0xfffffff,end=-1;
30 for(int i=0;i<n;i++)
31 {
32 scanf("%d%d",&data[i].s,&data[i].e);
33 data[i].s=data[i].s*2+1;
34 data[i].e=data[i].e*2-1;
35 start=min(start,data[i].s);
36 end=max(data[i].e,end);
37 }
38 sort(data,data+n,cmp);
39 int res=0;
40 for(int s=start;s<=start+10;s++)
41 {
42 int total=0,p=0;
43 priority_queue<node,vector<node>,cmp1> q;
44 for(int t=s;t<=end;t+=10)
45 {
46 while(p<n&&data[p].s<=t)
47 q.push(data[p++]);
48 while(!q.empty()&&q.top().e<t) q.pop();
49 if(!q.empty())
50 {
51 total++;
52 q.pop();
53 }
54 }
55 res=max(res,total);
56 }
57 printf("%d\n",res);
58 }
59 return 0;
60 }
61