资深守护
3254 借教室2
经验值：2400 时间限制：1000毫秒
题目描述 Description
元旦快到了，每个班级都要举行晚会，需要很多的空教室，教务老师认为：最好的策略应该是将空教室租给更多的班级。
显然，有可能存在不止一种满足要求的策略。 例如下面的例子。总共有 4 个班级。他们申请了借教室，并提出了他们所需占用教室的起止日期（如下表所示）。
开始日期 结束日期
班级1 ： 4 9
班级2 ： 9 11
班级3 ： 13 19
班级4 ： 10 17
上例中，最多将空教室借给两个班级。借教室策略分别是借给班级 1 和班级 3， 或是班级2 和班级 3，也可以是班级 1 和班级 4。注意空教室一天最多借给 一个班级，所以班级 1 和班级 2 不能同时借一个空教室，因为他们在第九天重合 了。
教务老师为了公平起见，决定按照如下的程序来确定选择何种借教室策略：首先，将借给班级数量最多的策略作为候选，将所有的班级按照他们发出请求的顺序编号。对于候选策略，将策略中的每个班级的编号按升序排列。最后，选出 其中字典序最小1的候选策略作为最终的策略。
例中，空教室最终将被借给班级 1 和班级 3：3 个候选策略是 {(1,3),(2,3),(1,4)}。而在字典序中(1,3)<(1,4)<(2,3)。 你的任务是帮助教务老师确定应该将会堂租借给哪些班级。
输入描述 Input Description
输入的第一行有一个整数 N，表示发出借教室申请的班级的个数。
第 2 到 第 N+1 行每行有 2 个整数。第 i+1 行的整数表示第 i 个班级申请租借的起始和终 止日期。对于每个班级的申请，起始日期为不小于 1 的整数，终止日期为不大于 10^9 的整数。
输出描述 Output Description
输出的第一行应有一个整数 M，表示最多可以借给多少个班级。第二行应列出 M 个数，表示最终将空教室租借给哪些班级。
样例输入 Sample Input
4 4 9 9 11 13 19 10 17
样例输出 Sample Output
2 1 3
数据范围及提示 Data Size & Hint
对于 50%的输入，N≤3000。
在所有输入中，N≤200000。
杜承俊在2021-08-10 20:20:52追加了内容
@汪恺恒 @侯平仄 @酷丁 @王泽宇@张帆
新手启示者
直接贪心是可以的
新手启示者
代码？
资深守护
- #include<bits/stdc++.h> using namespace std; int n; struct P{ int l,r; int t; }a[200010]; int f[200010]; bool cmp(P u,P v){ return u.r<v.r; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].l>>a[i].r; a[i].t=i; } sort(a+1,a+1+n,cmp); int cnt=1,r=a[1].r; f[cnt]=a[1].t; for(int i=2;i<=n;i++) if(a[i].l>r){ r=a[i].r; cnt++; f[cnt]=a[i].t; } sort(f+1,f+1+cnt); cout<<cnt<<endl; for(int i=1;i<=cnt;i++)cout<<f[i]<<" "; }
