区间调度问题

Description

有 n 项工作,每项工作分别在 si 时间开始,在 ti 时间结束。对于每项工作,你都可以选择参与否。如果选择了参与,那么自始至终都必须全程参与。此外,参与工作的时间段不能重叠(既是是开始的瞬间和结束的瞬间重叠也是不允许的)

你的目标是参与尽可能多的工作,那么最多能参与多少项工作呢?

Input

第一行输入一个数 n (1 ≤ n ≤ 100000),表示工作的数量
接下来的 n 行,第 1 + i (1 ≤ i ≤ n) 行包含两个数 si, ti (1 ≤ si ≤ ti ≤ 10^9),分别为起始时间和结束时间。

Output

输出为一行,包含一个整数,为能参与的工作数的最大值

Sample Input

5
1 3
2 5
4 7
6 9
8 10

Sample Output

3

Hint

每一次都选取结束时间最早的事件。因为与其他选择方案相比,该算法的选择方案在选取了相同数量的更早开始的工作时,
其最终结束时间不会比其他方案的更晚。所以,不存在选取更多工作的选择方案。
通过定义 compare 函数实现 sort() 的自定义排序规则。

题解

#include 
#include 
#include 
#include 
#include 
#include 
#define INF 100100
using namespace std;
int sum = 0;

struct node
{
    int start, end;
}arr[INF];

bool cmp(const node& i, const node& j)
{
    if (i.end > j.end)
        return 0;
    else
        if (i.end == j.end && i.start > j.start)
            return 0;
    return 1;
}

inline int find(int addr, int n)
{
    for (int i = addr + 1; i < n; i++)
        if (arr[i].start > arr[addr].end){
            return i;
        }
    return n+1;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &arr[i].start, &arr[i].end);
    sort(arr,arr+n,cmp);
    for (int addr = 0; addr < n; addr = find(addr, n))
        sum++;
    printf("%d\n", sum);
    return 0;
}

CC BY-SA 4.0 区间调度问题 by 小小泥娃的部落格 is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

发表评论