One (simplified) programming problem from the recent

 Asia-Pacific Informatics Olympiad 2009 competition

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
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 audi-
torium, 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.
A set of requests is a candidate to be chosen if it is of maximum
size. Your task is to help the marketing head decide the set of companies to
which the auditorium is to be rented.

Limits / Constraints:
In 50% of the inputs, N <= 3000. In all inputs, N <= 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.