Maximum Clique of an Interval Graph

Time limit1sMemory limit512 MB

Summary

Given N intervals, find a largest set of pairwise overlapping intervals, and output its size plus the vertex indices in lexicographically smallest order.

Level: Medium6 of 10
Topics: Sorting, Greedy, Intervals, Array
Solved: No attempts yet

Problem

In graph theory a clique is a subgraph that is complete. That is, it is a set of vertices in which every two vertices are joined by an edge. A maximum clique is a largest such set. Finding a maximum clique in a general graph is NP-hard.

You are given $N$ intervals. Interval $i$ starts at $S_i$ and ends at $E_i$ , and two intervals overlap when they share at least one point. These intervals define an interval graph. The interval graph has $N$ vertices, and vertex $i$ and vertex $j$ are joined by an edge exactly when interval $i$ and interval $j$ overlap. If the two intervals do not overlap, there is no edge between the two vertices.

For example, when the intervals are $[1, 3]$ , $[3, 7]$ , $[7, 10]$ , $[2, 5]$ , the interval graph looks like this.

The maximum clique of this interval graph is $\{1, 2, 4\}$ .

Given $N$ intervals, find a maximum clique of their interval graph.

Input

The first line has the number of intervals $N$ ( $1 \le N \le 300000$ ). Each of the next $N$ lines has two integers $S_i$ and $E_i$ , the start point and the end point of interval $i$ , separated by a space. ( $1 \le S_i < E_i \le 10^9$ )

Output

Print the size $s$ of a maximum clique on the first line. On the second line print the $s$ vertex numbers of that clique in increasing order, separated by spaces. If the graph has more than one maximum clique, print the one whose increasing list of vertex numbers is lexicographically smallest.

Examples2

Example 1
Input
```
4
1 3
3 7
7 10
2 5
```
Expected output
```
3
1 2 4
```
Example 2
Input
```
4
10 11
1 2
1 2
10 11
```
Expected output
```
2
1 4
```