#MYD3. 活动安排

活动安排

题目描述

有 n 个活动,第 i 个活动占用时间段 [a_i, b_i)。一个活动只有在它开始时刻不早于上一个所选活动的结束时刻时才能被选择(即先后两个活动满足 a_next ≥ b_prev)。每个活动至多选择一次,求最多能选择多少个活动。

输入格式

第一行一个整数 n。接下来 n 行,每行两个整数 a_i, b_i,表示活动的时间段。

输出格式

一行一个整数,表示最多可选择的活动数。

数据范围

1 ≤ n ≤ 100000,0 ≤ a_i < b_i ≤ 10^9。

样例

4
1 3
2 5
4 7
1 2
2

说明/提示

经典区间调度问题。

解析

思路:按结束时间 b 升序排序,依次贪心选择能与当前已选集合相容的最早结束活动。

证明:交换论证——若最优解首个活动不是结束最早的,替换为结束最早的不会使后续更差。

复杂度:O(n log n)。

来源

人工命题 · 三方对比实验