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
40 11 22 33 440 21 32 43 540 41 52 43 6
Sample Output
4123421 23 411 2 3 4题意：安排n门课程考试，为了防止作弊有交集的能安排在同一天。求一个安排是的考试的天数最少 题解：贪心的思想。先对课程考试的时间进行由小到大的排序，然后对每个区间进行考察，如果有交集的话那么合并区间。按照此法则一路贪心下去可得到最优解 输出结果的时候同一天安排的考试应该按先后顺序所以要进行二次排序
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int n;
int c[100000];
int m[100000];
struct lmx{
int x;
int y;
int pos;
int flag;
};
bool fan(lmx s,lmx t)
{
if(s.x==t.x) return s.y<t.y;
else return s.x<t.x;
}
bool gcd(lmx s,lmx t)
{
if(s.flag==t.flag) return s.pos<t.pos;
else return s.flag<t.flag;
}
lmx lm[100000];
int main()
{
int i,cnt,j,x,k;
while(scanf("%d",&n)!=EOF)
{
cnt=0;
x=0;
for(i=0;i<n;i++)
{
scanf("%d%d",&lm[i].x,&lm[i].y);
lm[i].pos=i;
lm[i].flag=0;
}
sort(lm,lm+n,fan);
memset(c,0,sizeof(c));
int top=0;
lm[0].flag=1;
for(i=1;i<n;i++)
{
if(lm[i].x<lm[i-1].y)
{
lm[i].x=max(lm[i].x,lm[i-1].x);
lm[i].y=min(lm[i].y,lm[i-1].y);
lm[i].flag=lm[i-1].flag;
}
else
{
lm[i].flag=1+lm[i-1].flag;
}
}
sort(lm,lm+n,gcd);
printf("%d\n",lm[n-1].flag);
int d=1;
int f=1;
for(i=0;i<n;i++)
{
if(lm[i].flag==d)
{
if(f==1)
{
printf("%d",lm[i].pos+1);
f=2;
}
else printf(" %d",lm[i].pos+1);
}
else
{
printf("\n");
d+=1;
printf("%d",lm[i].pos+1);
}
}
puts("");
}
return 0;
}