APIO '09 P2 - The Siruseri Convention Centre

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.5s
Memory limit: 64M

Problem type

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 the auditorium out to as many different 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.

Start End
Company 1 4 9
Company 2 9 11
Company 3 13 19
Company 4 10 17

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.

Lexicographic order is dictionary order, so list l_1 is smaller than list l_2 if l_1 is a prefix of l_2 or if at the first position j where l_1 and l_2 differ, l_1[j] < l_2[j].

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 format

The first line contains an integer N, 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.

Output format

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.

Test Data

In 50% of the inputs, N \le 3000. In all inputs, N \le 200000. For each company’s request, the starting day is always greater than or equal to 1 and the ending day never exceeds 10^9.

Sample input

4
4 9
9 11
13 19
10 17

Sample output

2
1 3

Comments

There are no comments at the moment.