Algoogle

Algorithm for Programming Contest

PKU 3190 Stall Reservations

Category: PKU Tag: greedy

Stall Reservations

問題概要


各牛に対して閉区間が与えられるのでどの牛も重ならないように牛舎を割り当てる.
そのときの必要な最大の牛舎の数と, その割り当て方を求める.

解法


始まりが早い順に入れていく.

コード


(3190.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <algorithm>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>

using namespace std;

typedef pair<int,int> pii;

int N;
pii in[50010], out[50010];
int ans[50010];
int sz = 0;

int main(){
    scanf("%d", &N);
    priority_queue<int, vector<int>, greater<int> > que;
    for(int i = 0; i < N; i++){
        int a, b; scanf("%d%d", &a, &b);
        b++;
        in[i] = pii(a, i); out[i] = pii(b, i);
        que.push(i+1);
    }
    sort(in, in+N); sort(out, out+N);
    int i = 0, o = 0;
    while(i < N && o < N){
        if(in[i].first < out[o].first){
            ans[in[i].second] = que.top(); que.pop();
            sz = max(sz, ans[in[i].second]);
            i++;
        }else que.push(ans[out[o++].second]);
    }

    printf("%d\n", sz);
    for(int i = 0; i < N; i++)
        printf("%d\n", ans[i]);
    return 0;
}

Comments