P3626 [APIO2009] Conference Center

The Siruseri government has built a new conference center. Many companies are interested in renting its hall and wish to hold meetings there. A client will rent the hall only if they can exclusively occupy the entire hall during their meeting. The sales manager believes the best strategy is to rent the hall to as many clients as possible. Obviously, there may be more than one valid strategy. For example, consider the following case with 4 companies. They have requested to rent the hall with given start and end dates (as shown in the table below). ```cpp 开始日期 结束日期 公司1 4 9 公司2 9 11 公司3 13 19 公司4 10 17 ``` In this example, the hall can be rented to at most two companies. Possible strategies include renting to companies 1 and 3, companies 2 and 3, or companies 1 and 4. Note that the conference center can be rented to at most one company per day, so companies 1 and 2 cannot both rent the hall because they overlap on day 9. To be fair, the sales manager decides to determine the final strategy as follows: first, consider all strategies that rent to the maximum number of clients; number all companies according to the order of their requests. For each candidate strategy, sort the selected company indices in ascending order. Finally, choose the lexicographically smallest candidate strategy as the final strategy. In the example, the hall will be rented to companies 1 and 3: the 3 candidate strategies are {(1, 3), (2, 3), (1, 4)}, and in lexicographic order, (1, 3) < (1, 4) < (2, 3). Your task is to help the sales manager determine which companies should be granted the rental.

The first line contains an integer $N$, the number of companies that requested to rent the hall. Each of the next $N$ lines contains 2 integers. The integers on line $i + 1$ give the requested start and end dates for company $i$. For each request, the start date is an integer not less than 1, and the end date is an integer not greater than $10^9$.

The first line should contain an integer $M$, the maximum number of companies that can be served. The second line should list $M$ integers, indicating which companies will be granted the rental (in ascending order, forming the final strategy).

- For 50% of the input, $N \le 3000$. - For all inputs, $N \le 200000$. Translated by ChatGPT 5