Asia-Pacific Informatics Olympiad 2009

Problem 2: The Siruseri Convention Centre

The Government of Siruseri has constructed a new Convention Centre. A number of companies have expressed an interest in renting the auditorium in the Convention Centre to hold their conferences.

A client is willing to rent the auditorium only if it is granted to him exclusively for the entire duration of his conference. The marketing head of the Convention Centre has decided that the best strategy would be to rent to as many clients as possible. Clearly there may be more than one way to do this.

Consider, for instance, the following example with 4 companies. The companies are listed in the order in which they made requests for the auditorium, with the duration of each conference indicated by the starting and ending day.

In this example, it is possible to rent out the auditorium to a maximum of two companies. The choices are 1 and 3, or 2 and 3, or 1 and 4. Note that the auditorium can be rented out to only one company on any day. Thus, 1 and 2 cannot both be granted the auditorium because their requests overlap on day 9.

The marketing head believes in fairness and he has decided on the following procedure to choose the combination to which he will rent out the auditorium. A set of requests is a candidate to be chosen if it is of maximum size. Observe that the companies are numbered according to the order in which they make their requests. The companies in each candidate set are listed out in ascending order. Among these, the lexicographically smallest candidate set is chosen.

In this example the auditorium will be rented out to companies 1 and 3—the three candidate sets are {(1, 3), (2, 3), (1, 4)} and (1, 3) < (1, 4) < (2, 3) when ordered lexicographically.

Your task is to help the marketing head decide the set of companies to which the auditorium is to be rented.

Input

The first line contains an integer N (N ≤ 200000), the number of companies that have applied for renting the auditorium. Lines 2 to N+1 contain two integers. The integers on line i+1 are the starting and ending dates for the request from company i. The starting day is always at least 1 and the ending day never exceeds 10⁹.

Output

The first line of the output should consist of an integer M, the maximum number of companies to which the auditorium can be rented. This should be followed by a line containing M integers listing the identities of the companies that appear in the lexicographically smallest such set.

Sample Input

4
4 9
9 11
13 19
10 17

Sample Output

2
1 3

Note on grading

In 50% of the test cases, N ≤ 3000.

All Submissions
Best Solutions

Point Value: 40 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: Jul 22, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Hm...I'm not sure what's wrong, but I'm getting random WA's though my program produces the correct output... (Submitting the same solution but getting different cases WA, not using random)