首页 > 代码库 > Final Exam Arrangement

Final Exam Arrangement

2024-07-14 02:09:54   220人阅读

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


扫描线

把时间点排序，若时间相同，则右端点优先排序，因为是开区间

顺序扫描每个点，在遇到没处理过的第一个右端点前，所扫描到的左端点所代表的考试均可放在一天



//#pragma comment(linker, "/STACK:102400000,102400000")
//HEAD
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>

#include <queue>
#include <string>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <cstdlib>

using namespace std;
//LOOP
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FED(i, b, a) for(int i = (b); i>= (a); --i)
#define REP(i, N) for(int i = 0; i < (N); ++i)
#define CLR(A,value) memset(A,value,sizeof(A))
//STL
#define PB push_back
//INPUT
#define RI(n) scanf("%d", &n)
#define RII(n, m) scanf("%d%d", &n, &m)
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define RS(s) scanf("%s", s)


#define FF(i, a, b) for(int i = (a); i < (b); ++i)
#define FD(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define CPY(a, b) memcpy(a, b, sizeof(a))
#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define EQ(a, b) (fabs((a) - (b)) <= 1e-10)
#define ALL(c) (c).begin(), (c).end()
#define SZ(V) (int)V.size()
#define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p)
#define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q)
#define WI(n) printf("%d\n", n)
#define WS(s) printf("%s\n", s)

#define debugt(a) cout << (#a) << "=" << a << " ";
#define debugI(a) debugt(a) cout << endl
#define debugII(a, b) debugt(a) debugt(b) cout << endl
#define debugIII(a, b, c) debugt(a) debugt(b) debugt(c) cout << endl
#define debugIV(a, b, c, d) debugt(a) debugt(b) debugt(c) debugt(d) cout << endl
#define debugV(a, b, c, d, e) debugt(a) debugt(b) debugt(c) debugt(d) debugt(e) cout << endl

typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 100010;
typedef vector <int> VI;
typedef unsigned long long ULL;
const double eps = 1e-10;
const LL MOD = 1e9 + 7;

struct course{
    int w, id;
    bool l;
    bool operator < (const course& a) const{
        if (w == a.w)
            return l < a.l;
        return w < a.w;
    }
}c[maxn * 2 + 10];
VI ans[maxn];
bool use[maxn * 2];

int main()
{
    //freopen("0.txt", "r", stdin);
    int n;
    while (~RI(n))
    {
        REP(i, n)
        {
            RII(c[i * 2].w, c[i * 2 + 1].w);
            c[i * 2].id = c[i * 2 + 1].id = i + 1;
            c[i * 2].l = 1, c[i * 2 + 1].l = 0;
        }
        sort(c, c + 2 * n);
        REP(i, n + 1)   ans[i].clear();
        CLR(use, 0);
        int cnt = 0, j;
        REP(i, 2 * n)
        {
            if (use[c[i].id]) continue;
            j = i;
            while (j < 2 * n)
            {
                if (use[c[j].id])
                {
                    j++;
                    continue;
                }
                if (!use[c[j].id] && c[j].l == 0)
                    break;
                j++;
            }
            FF(k, i, j)
                if (c[k].l)
                {
                    ans[cnt].PB(c[k].id);
                    use[c[k].id] = 1;
                }
            cnt++;
            i = j;
        }
        WI(cnt);
        REP(i, cnt)
        {
            sort(ans[i].begin(), ans[i].end());
            REP(j, ans[i].size())
            {
                if (j) printf(" ");
                printf("%d", ans[i][j]);
            }
            puts("");
        }
        puts("");
    }
    return 0;
}



联系
我们