POJ 3190 Stall Reservations(贪心)

Description

给出N个区间，将其不重叠地放在数轴上，至少需要几个数轴？

[1, 2]，[2, 3]算作重叠

Analyze

贪心：若一个区间能接在另一个区间的后面，则二者可共用一个数轴

按区间左界从小到大排序，左界相同右界小的在前

第一个占用一条数轴，放入某个容器里。从第二个开始遍历，找出容器里(容器里都是安排好的区间)右界最小的区间，若其小于当前区间的左界，则当前区间可与该区间共用同一数轴，将那个区间拿出来，把这个区间放进去

每次都要找出容器中右界最小的区间，那么该容器可用优先队列充当

Code

#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

struct node
{
    int l, r, id, after_id, num;
    bool operator <(const node & a)const
    {
        if(a.r == r)
            return a.l < l;
        return a.r < r;
    }
} a[60005];

bool cmp(node a, node b)
{
    if(a.l != b.l)
        return a.l < b.l;
    return a.r < b.r;
}

bool cmp_id(node a, node b)
{
    return a.id < b.id;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &a[i].l, &a[i].r), a[i].id = i;
    sort(a, a + n, cmp);

    for(int i = 0; i < n; ++i)
        a[i].after_id = i;

    int ans = 1;
    a[0].num = ans;
    priority_queue<node> q;
    q.push(a[0]);
    for(int i = 1; i < n; ++i)
    {
        if(!q.empty() && a[i].l > q.top().r)
        {
            a[i].num = a[ q.top().after_id ].num;
            q.pop();
        }
        else
            a[i].num = ++ans;
        q.push(a[i]);
    }
    sort(a, a + n, cmp_id);
    cout << ans << '\n';
    for(int i = 0; i < n; ++i)
        cout << a[i].num << '\n';
    return 0;
}