← 返回题目列表

AtCoder · arc032_3

C. 工作计划

中文机器翻译题面 查看原题

問題文

Daiku Cho 是一名木匠。 我被要求做 N 工作。i 第一份工作是时间 以 a_i 开头, 它以b_i 结尾。

Cho 先生无法同时从事多项工作,因此他希望选择尽可能多的工作,以便工作时间不会重叠。但是,您可以在完成后立即开始从事另一项工作。

当有多种方法可供选择时,我想选择一种方法,使得按开始时间顺序排列的所选作业编号的列按字典顺序最小。

曹先生是一名木匠,他的工作很出色,但他似乎不擅长管理自己的日程安排。请找出曹先生所承担的最佳任务组合。

然而,长度 L 栏 A=\{a_1,a_2,…,a_L\} 和 将其放在 B=\{b_1,b_2,…,b_L\} 按字典顺序 A 是 从 B 小于

  • i<k 可以访问第 a_i=b_i
  • i=k 可以访问第 a_i<b_i

这意味着 k(1≦k≦L) 存在。


入力

输入将以以下形式通过标准输入给出。

N
a_1 b_1
a_2 b_2
:
a_N b_N
  • 1 行是一个整数,表示 Cho 先生被要求执行的任务数。 N (1 ≦ N ≦ 100,000) 。 来自行
  • 2 第 N 行提供有关 Cho 先生被要求执行的任务的信息。这几天之一 i 行中,i 个任务的开始时间和结束时间 2 整数 编写一个程序来查找 a_i, b_i(0 ≦ a_i < b_i ≦ 1,000,000) 以空格分隔。

出力

1 在第 1 行中,打印 Cho 先生将承担的作业数量。

2 第一行按时间降序列出了曹先生将承担的任务。 1 用两个空格分隔并输出。

不要忘记最后的换行符。另外,不要在末尾添加额外的空格。


入力例1

4
0 5
0 3
3 7
5 10

出力例1

2
1 4

曹先生是最大的 2 您可以选择一项工作。如何选择 3 是的,曹先生正在工作。 1 和 将其放在 4,或工作 您可以选择 2 和 将其放在 3,或工作 您可以选择 2 和 将其放在 4 。 其中,按字典顺序排列最小的是工作。 当您选择 1 和 将其放在 4 时。因为那些工作号码 工作开始时间顺序 当排列在 中时 \{1,4\} ,这是字典顺序中的最小值(于 21:12 更正)。


入力例2

5
0 5
0 3
3 7
5 10
7 12

出力例2

3
2 3 5

入力例3

8
1 5
3 9
2 5
1 2
8 10
9 11
7 15
10 14

出力例3

4
4 3 5 8