ZOJ 3721 Final Exam Arrangement（模拟+贪心）

﹏ヽ暗。殇╰゛Y 2022-06-10 11:27 171阅读 0赞

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+1*th line contains **s** and **t** of the interval **\[s, t)** for the *i*th 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+1*th line contains the numbers of courses whose final exam is arranged on the *i*th 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

题解：

题意：

给n门课的上课起始时间，让你为每门课安排一场考试，如果这些课的上课时间有重合部分，这些课就可以一起考试，最后按时间顺序输出他们的考试安排，同一天的考试在同一行

思路：

题意很难懂，懂了也觉得很奇怪，安排得莫名其妙，不过解决起来很简单，就是按照开始时间排一下序，排好以后如果这天的课的开始时间小于前一天的结束时间，那么就放在同一天考，否则就新开一天考试

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    struct edge
    {
        int s,t,id,n;
    }a[100005];
    int cmp(edge x,edge y)//按开始时间排序
    {
        return x.s<y.s;
    }
    int main()
    {
        int n,sum,s,t,i,j;
        while(scanf("%d",&n)!=EOF)
        {
            for(i=1;i<=n;i++)
            {
                scanf("%d%d",&a[i].s,&a[i].t);
                a[i].n=i;//记录课的下标
            }
            sort(a+1,a+n+1,cmp);
            a[1].id=1,sum=1,s=a[1].s,t=a[1].t;//先把第一种作为初始情况
            for(i=2;i<=n;i++)
            {
                if(a[i].s<t)//如果开始时间比前一天的结束时间早，并为同一天考试
                {
                    s=a[i].s;
                    if(a[i].t<t)
                        t=a[i].t;
                    a[i].id=sum;
                }
                else//否则天数++
                {
                    s=a[i].s;
                    t=a[i].t;
                    sum++;
                    a[i].id=sum;
                }
            }
            printf("%d\n%d",sum,a[1].n);//输出第一天考的科目
            for(i=2;i<=n;i++)//输出剩下天数考的科目
            {
                if(a[i].id==a[i-1].id)
                {
                    printf(" %d",a[i].n);
                }
                else
                {
                    printf("\n%d",a[i].n);
                }
            }
            printf("\n\n");
        }
        return 0;
    }