Consider the intervals as vertices and add an edge between vertices if they overlap. This gives an interval graph the problem is to find a lexicographically smallest maximal independent set (MIS) of such an interval graph.

Finding a maximal independent set: Finding a maximum sized candidate is easy, a greedy algorithm suffices. Sort the intervals by increasing order of endpoints and process them in this order. Include an interval if it does not overlap with any of the intervals selected earlier. This can be done in linear time after the sorting.

Lexicographically earliest: ~\mathcal O(N^2)~ Now, to find the lexicographically least among all maximum independent sets, where the order is defined by the order in which the vertices appear in the input. Greedily add the vertices in the order of their appearance in the input, and find out at each step if the current set can be extended to an independent set of maximum size (this can be done in linear time using the algorithm outlined above.) This gives an ~\mathcal O(N^2)~ algorithm.

Lexicographically earliest: ~\mathcal O(N \log N)~ For clarity in the explanation, assume that no interval is completely contained in another interval. This assumption can be eliminated with a somewhat more elaborate argument along the same lines and the details are omitted here.

Preliminaries:

• We will think of the intervals as nodes of a graph. Two nodes have an edge if the corresponding intervals intersect. The label of node ~[a_i, b_i]~ is ~i~.
• The required solution is the lexicographically earliest maximum independent set. By ~MIS(S)~, where ~S~ is a subset of ~1, \dots, n~ we will mean any MIS of the subgraph induced by ~S~.
• Define ~right(i) := \min\{j > i \mid i\text{ and }j\text{ don't have an edge}\}~.

Observation 1 Our simple solution to (non-lexicographic) MIS shows that

$$\displaystyle \{1, right(1), right(right(1)), \dots\}$$

is a solution.

Subroutine that takes ~i < j~ and outputs ~|MIS\{i, i+1, \dots, j\}|~ in ~\log n~ time: Using the first observation, the size of the MIS of ~\{i, i+1, \dots, j\}~ is ~1+\max\{k : right^k(i) \le j\}~. This subroutine will essentially guess the bits of the correct ~k~. The data structure to do this (created in the preprocessing stage) is ~\log n~ arrays ~Right[1][*], \dots, Right[\log n][*]~ where ~Right[k][t] := right^{2^k}[t]~.

Main Program First compute the size of the MIS, ~s* = |MIS\{1, \dots, n\}|~. Take node ~i_0~ with earliest time. Neighbors of ~i_0~ are ~\{i, i+1, \dots, j\}~ for some ~i \le i_0 \le j~. These ~i, j~ can be found by binary search in ~\log n~ time. To test whether ~i_0~ can be included in a MIS, we need to check if ~s* = |MIS\{1, \dots, i-1\}|+1+|MIS\{j+1, \dots, n\}|~. This can be done in ~\log n~ time using the subroutine.

Suppose ~i_0~ passed the test. Take the next node ~i_1~ (by input ordering). Now we first locate (in ~\log n~ time through binary search) which of the two sides ~\{1, \dots, i-1\}~ or ~\{j+1, \dots, n\}~ does ~i_1~ belong to. If it belongs to neither, then ~i_1~ was a neighbor of ~i_0~, and so fails the test. Otherwise, suppose ~i_1~ was in ~\{j+1, \dots, n\}~, and its neighbors were ~\{i', i'+1, \dots, j'\}~ where ~j+1 \le i' \le i_1 \le j' \le n~. Now we need to check if ~|MIS\{j+1, \dots, n\}| = |MIS\{j+1, \dots, i'-1\}|+1+|MIS\{j'+1, \dots, n\}|~.

The data structure required for this part is a segment tree (or anything that can support insertions, and queries asking for the smallest element in the data structure larger than a number given in the query).