Finding the minimum subset within a cycle

Question

Suppose we have a set $A$ of pairs $(a,b)$ such that $a$ and $b$ are real numbers defined in the interval $[c,d]$. Assume no two values are identical. For $(a,b)$, if $a > b$, the range is $[a,d] \cup [c,b]$; otherwise, it is $[a,b]$. What is the most efficient algorithm to find the smallest subset $B \subseteq A$ such that, for any value within the range of any pair in $A$, the value is also within the range of any pair in $B$.

There exists an $O(n \log n)$ algorithm to find the smallest subset when, for any pair, $a$ is strictly less than $b$. I can run this algorithm for each pair to determine my solution. However, what is a more efficient algorithm to obtain the smallest subset?

Answer 1

Using Kaveh's reduction in this related question, we only have to solve the case where the given intervals cover the entire circle $[c,d]$.

Here's an algorithm that almost calculates the optimum, in $O(n\log n)$. Replace each interval $[a,d] \cup [c,b]$ by the two intervals $[a,d],[c,b]$, and now solve the original problem. Let $O$ be the optimum of the original problem, and $S$ be the optimum of the new problem. I claim that $S-1 \leq O \leq S$.

First, given any solution to the new problem, we can find a solution to the old problem with the same cost, showing that $O \leq S$. For the other direction, take some optimal solution. If it doesn't use any split interval, then $S = O$. Otherwise, let $I_\min$ be the split interval minimizing $a$, and let $I_\max$ be the split interval maximizing $b$. If we drop all other split intervals, then whatever remains is still a cover of the circle. If $I_\min \neq I_\max$ then $S = O$, and otherwise all we know is that $S \leq O+1$.

It's plausible that this algorithm can be adapted somehow to actually find the optimum. (Most algorithms that work on interval graphs also work on circular-arc graphs.)