2 shunfurh shunfurh 于 2017.08.27 21:20 提问

Final Exam Arrangement

In Zhejiang University, there are N different courses labeled from 1 to N. Each course has its own time slot during the week. We can represent the time slot of a course by an left-closed right-open interval [s, t).

Now we are going to arrange the final exam time of all the courses.

The final exam period will contain multiple days. In each day, multiple final exams will be held simultaneously. If two courses' time slots are not overlapped, there may be students who are attending both of them, so we cannot arrange their final exams at the same day.

Now you're to arrange the final exam period, to make the total days as small as possible.

Input

There are multiple test cases separated by blank lines.

For each ease, the 1st line contains one integer N(1<=N<=100000).

Then N lines, the i+1th line contains s and t of the interval [s, t) for the ith course.(0<=s<t<=231-1)

There is a blank line after each test case.

Output

For each case, the 1st line contains the days P in the shortest final exam period.

Next P lines, the i+1th line contains the numbers of courses whose final exam is arranged on the ith day separated by one space.

Output a blank line after each test case.

Sample Input

4
0 1
1 2
2 3
3 4

4
0 2
1 3
2 4
3 5

4
0 4
1 5
2 4
3 6

Sample Output

4
1
2
3
4

2
1 2
3 4

1
1 2 3 4

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.10 23:53
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Final Exam Arrangement
In Zhejiang University, there are N different courses labeled from 1 to N. Each course has its own time slot during the week. We can represent the time slot of a course by an left-closed right-open in
CCNA第一学期各章考试和final exam
CCNA第一学期网络基础知识各章考试和final exam,准确率在98%以上
SSD3 Final Exam 答案
SSD3 Final Exam 答案 SSD3 Final Exam 答案 SSD3 Final Exam 答案 SSD3 Final Exam 答案
Final Exam Arrangement(zju5044,贪心)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5044 ZOJ Problem Set - 3721 Final Exam Arrangement Time Limit: 4 Seconds      Memory Limit: 65536 KB      Special Judge In Zhejiang Unive
cisco ccna2 final exam 2及答案
cisco ccna2 final exam 2原题及答案,或许对你有用!
ZOJ 3721—— Final Exam Arrangement
题意为安排时间相交的两门课安排在同一天考试,先排序
ZOJ:3721 Final Exam Arrangement
问你有交集(覆盖)的区间一共有多少组并输出。   还是区间问题。   写码能力太弱,思路很容易想到了但是写却写了半天。中间还超时了好几次,所以最后我连int数组都没开。   最后还是AC了,不容易。。   #include #include #include #include #include #include using namespace std; s
ZOJ 3717: Final Exam Arrangement
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3721 题意: 给出若干课程的上课区间, 若两门课程的上课时间不重叠,则可能有学生同时选修这两门课程,因此不能安排在一天考试。 问至少要安排多少天考试,并输出方案 算法: 线段树优化的DP 首先把课程按照结束时间排序。 对于一个课程,
CCNA2 思科第二学期 v2.0 ERouting final Exam 第一套第二套第三套(三合一中文版)
要密码联系:1103180364或18755611485!天下没有免费的午餐,此文件也算是本人辛辛苦苦的成果啊!所以呢!需要报酬!不多8Q币报酬 CCNA2 思科第二学期 v2.0 ERouting final Exam 第一套第二套第三套(三合一中文版)
CCNA第二学期各章考试和final exam
最新CCNA第二学期LAN交换各章考试和final exam。准确率在98%以上