会场安排问题

coding>C++
716 词

题目描述

假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。）

算法设计：对于给定的 k 个待安排的活动，计算使用最少会场的时间表。

输入

输入第一行有 1 个正整数 k，表示有 k 个待安排的活动。接下来的 k 行中，每行有 2 个正整数，分别表示 k 个待安排的活动开始时间和结束时间。时间以 0 点开始的分钟计。

输出

将计算出的最少会场数输出

样例输入

1
2
3
4
5
6
5
1 23
12 28
25 35
27 80
36 50

样例输出

1
3

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, i, Begins[10002], Ends[10002];
    cin >> n;
    for (i = 0; i < n; i++)
        cin >> Begins[i] >> Ends[i];
    sort(Begins, Begins + n);
    sort(Ends, Ends + n);
    int j = 0, ans = 0;
    for (i = 0; i < n; i++)
        if (Begins[i] < Ends[j])
            ans++;
        else
            j++;
    cout << ans << endl;
    return 0;
}