挑战程序设计—— 区间调度问题

有 nn 个工作，每个工作的开始和结束时间分别为 s_isi​，t_iti​。

当选中了一个工作就要从到尾完成，不能中断。

选择多个工作的时候，工作之间不能有重叠，即使是开始和结束的瞬间也不能重叠。

现在让我们求出最多能选择多少个工作？

多组测试数据，以 EOF 结束每组测试：

第一行是整数 n(1 leq n leq 10^5)n(1≤n≤105)接下来 nn 行，每行两个整数，表示一个工作的开始时间 s_isi​ 和 结束时间 t_iti​1 leq s_i leq t_i leq 10^91≤si​≤ti​≤109数据保证：多组测试数据的 nn 总和不超过 10^5105 输出

输出多行，每行一个整数，表示一组测试数据中，最多能选多少个工作

样例 1

输入

5
1 3
2 5
4 7
6 9
8 10

输出

3

#include
using namespace std;

int n;
struct Time
{
    int start;
    int end;
};

Time t[100001];

bool cmp(Time a,Time b)
{
    if(a.end>n)
    {
        for(int i=0;i>t[i].start>>t[i].end;
        sort(t,t+n,cmp);
        int count=0;
        int endd=0;
        for(int i=0;iendd)
            {
                count++;
                endd=t[i].end;
            }
    cout< 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714658.html