poj3190(Stall Reservations)

Description

Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows.

Help FJ by determining:

The minimum number of stalls required in the barn so that each cow can have her private milking period
An assignment of cows to these stalls over time

Many answers are correct for each test dataset; a program will grade your answer.

Input

Line 1: A single integer, N

Lines 2..N+1: Line i+1 describes cow i's milking interval with two space-separated integers.

Output

Line 1: The minimum number of stalls the barn must have.

Lines 2..N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period.

Sample Input

Sample Output

Hint

Explanation of the sample:

Here's a graphical schedule for this output:

Time     1  2  3  4  5  6  7  8  9 10 
Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>

Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..

Stall 3 .. .. c3>>>>>>>>> .. .. .. ..

Stall 4 .. .. .. c5>>>>>>>>> .. .. ..

Other outputs using the same number of stalls are possible.

将n个区间分成最少的组，使每个组的区间没有重合。按区间左端点从小到大排序，用优先队列记录stall及其最右端端点，优先队列按照右端点从小到大排序。每次取出右端点最小的stall，如果当前区间与之有重合，则新增一个stall，否则更新该stall右端点。

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
const int maxn = 50010;

struct stall
{
    int name, last;
    bool operator < (const stall& b) const
    {
        return last > b.last;
    }
};

struct cow
{
    int name, start, over;
    bool operator < (const cow& b) const
    {
        return start < b.start;
    }
};

int main()
{
    int n;
    cin >> n;
    cow s[maxn];
    for (int i = 0; i < n; ++i)
    {
        scanf("%d%d", &s[i].start, &s[i].over);
        s[i].name = i;
    }
    sort(s, s+n);
    priority_queue<stall> q;
    int ans = 1, num[maxn];
    num[s[0].name] = 1;
    q.push({1, s[0].over});
    for (int i = 1; i < n; ++i)
    {
        stall tmp = q.top();
        q.pop();
        if (s[i].start > tmp.last)
        {
            num[s[i].name] = tmp.name;
            tmp.last = s[i].over;
            q.push(tmp);
        }
        else
        {
            num[s[i].name] = ++ans;
            q.push(tmp);
            q.push({ans, s[i].over});
        }
    }
    printf("%d\n", ans);
    for (int i = 0; i < n; ++i)
        printf("%d\n", num[i]);
    return 0;
}

算法码上来文章被收录于专栏

公众号「算法码上来」。godweiyang带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。