While reading a paper (On the k-coloring of intervals), I came upon the following description:

"Input: An integer k, and a set of n intervals sorted by right and left endpoints. The intervals are indexed in order of increasing right endpoint, and it is assumed that all endpoints are positive integers."

What does it mean that they are sorted by "right and left endpoints"? Does it mean that each interval is on the form (left endpoint, right endpoint)?


Yes, you are right. The intervals are of the form (left endpoint, right endpoint).

First, consider the following statement:

The intervals are indexed in order of increasing right endpoint

It means that given a set of intervals $I_{1}, \dotsc, I_{n}$, the $(\textrm{right endpoint of }I_{i})$ $\leq$ $(\textrm{right endpoint of }I_{j})$ for any $i \leq j$ and $i,j \in \{1, \dotsc,n\}$.

Similarly, you can define the sorted order based on the left endpoints. However, the sorted order based on these two criteria could be different.

Now, consider the following statement:

a set of n intervals sorted by right and left endpoints

This statement is a bit unclear since the sorted order by left endpoints could be different from the sorted order by right endpoints. However, in Section 1(Introduction) of their paper, they also mention the following statement: "set of $n$ sorted intervals (the $2n$ endpoints of the intervals are sorted). ". Therefore, the sorting by "right and left endpoint" simply means that you are sorting the set of all $2 \cdot n$ points together, i.e., the set: $\{ \ell_{1}, r_{1}, \dotsc, \ell_{n}, r_{n} \}$ is given in sorted order irrespective of point being a left or right endpoint. Furthermore, using this sorted set you can easily recover the sorting of intervals based on (right endpoint) or (left endpoint) in linear time i.e., $O(n)$. This does not change the running time of their coloring algorithm which is $O(n + k)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.