Problem : 234 - Convention

Problem Statistics

Solved Member: 8　　Submission: 68　　User Tried: 10

Statement:

Siruseri政府建造了一座新的會議中心。許多公司對租借會議中心的會堂很感興趣，他們希望能夠在裡面舉行會議。

對於一個客戶而言，僅當在開會時能夠獨自佔用整個會堂，他才會租借會堂。會議中心的銷售主管認為：最好的策略應該是將會堂租借給盡可能多的客戶。顯然，有可能存在不止一種滿足要求的策略。

例如下面的例子。總共有4個公司。他們對租借會堂發出了請求，並提出了他們所需佔用會堂的起止日期（如下表所示）。

	開始日期	結束日期
公司 1	4	9
公司 2	9	11
公司 3	13	19
公司 4	10	17

上例中，最多將會堂租借給兩家公司。
租借策略分別是租給公司1和公司3，或是公司2和公司3，也可以是公司1和公司4。
注意會議中心一天最多租借給一個公司，所以公司1和公司2不能同時租借會議中心，因為他們在第九天重合了。

銷售主管為了公平起見，決定按照如下的程式來確定選擇何種租借策略：
首先，將租借給客戶數量最多的策略作為候選，將所有的公司按照他們發出請求的順序編號。
對於候選策略，將策略中的每家公司的編號按昇冪排列。
最後，選出其中字典序最小的候選策略作為最終的策略。

例中，會堂最終將被租借給公司1和公司3：
三個候選策略是{(1,3),(2,3),(1,4)}。而在字典序中(1,3)<(1,4)<(2,3)。
你的任務是幫助銷售主管確定應該將會堂租借給哪些公司。

註：字典序指在字典中排列的順序，如果序列l₁是序列l₂的前綴，或者對於l1和l2的第一個不同位置j，l₁[j]2[j]，則l₁比l₂小

Input:Output:

輸入的第一行有一個整數 N，表示發出租借會堂申請的公司的個數。
第 2 到第 N+1 行每行有 2 個整數。
第 i+1 行的整數表示第 i 家公司申請租借的起始和終止日期。
對於每個公司的申請，起始日期為不小於 1 的整數，終止日期為不大於10⁹的整數。

對於 50%的輸入，N≤3000。在所有輸入中，N≤200000

輸出的第一行應有一個整數 M，表示最多可以租借給多少家公司。
第二行應列出 M 個數，每個數字後面請接一個空白，表示最終將會堂租借給哪些公司。

Sample Input:Sample Output:

4
4 9
9 11
13 19
10 17

2
1 3

(3後面有一個空白)

Source:

APIO 2009

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	3000ms	65536kb
1	3000ms	65536kb	2
2	3000ms	65536kb	2
3	3000ms	65536kb	2
4	3000ms	65536kb	2
5	3000ms	65536kb	2
6	3000ms	65536kb	5
7	3000ms	65536kb	5
8	3000ms	65536kb	5
9	3000ms	65536kb	5
10	3000ms	65536kb	5
11	3000ms	65536kb	5
12	3000ms	65536kb	5
13	3000ms	65536kb	5
14	3000ms	65536kb	5
15	3000ms	65536kb	5
16	3000ms	65536kb	5
17	3000ms	65536kb	5
18	3000ms	65536kb	5
19	3000ms	65536kb	5
20	3000ms	65536kb	5
21	3000ms	65536kb	5
22	3000ms	65536kb	5
23	3000ms	65536kb	5