3
$\begingroup$

Consider a variant of interval scheduling except now the intervals are arcs on a circle. The goal is to find the maximum number of arcs that do not overlap. Let $C$ be the circle on the plane centered at the origin with unit radius. Let $A_1, ..., A_n$ be a collection of arcs on the circle where an arc $A_i$ is specified by two angles $\alpha_i\in [0,2\pi]$ and $\beta_i\in [0,2\pi]$: the arc starts at the point on the circle 𝐶 with angle $\alpha_i$ and goes counter-clockwise till the point on $C$ at angle $\beta_i$. Two arcs overlap if they share a point on the circle.

I want the maximum number of non-overlapping arcs in the given set of arcs.

One way to do it is to first sort the intervals by start angle in $O(n\log n)$ time. Then, for each arc $A_i$, assume it is taken, and mark all arcs that intersect it as "invalid". Then, run the normal interval scheduling algorithm on the remaining "valid" arcs which won't overlap $A_i$ and the maximum end time will not intersect the first start time. This takes $O(n)$ per arc, leading to an $O(n^2)$ time algorithm when taking the maximum across all possible arc selections.

My question is, can we do better? Is $O(n\log n)$ also achievable on the circular case?

$\endgroup$
1
  • $\begingroup$ Nice variation. It could appear in a practical setting where there are events/activities that happen periodically every 24 hours. How can we select the maximum number of them so that they can happen without overlapping? $\endgroup$
    – John L.
    Sep 20 '21 at 1:17
2
$\begingroup$

Yes.

What we need to do is, basically, running the $O(n^2)$ algorithm provided in the question, but without unnecessary intervals and redundant steps.


Here is the gist of an $O(n\log n)$ algorithm.

Assume each interval is expressed as $[\alpha, \beta]$, where $0\le\alpha\lt 2\pi$ and $\alpha\le \beta\lt \alpha+2\pi$. It means all the points on the circle whose angles are between $\alpha$ and $\beta$.

If an interval is contained in another interval, remove the containing interval. This operation will not decrease the maximum number of non-overlapping arcs. Repeat this operation as long as possible. The whole removing process can be done in $O(n\log n)$ time by sorting the intervals by ascending start angle primarily and descending end angle secondarily, and then processing each interval in order.

Now no interval contains another interval and the remaining intervals are sorted both by start angle and by end angle (both orders are strictly ascending). Pick an arbitrary interval (that has not been removed). For example, let us pick the first one remaining. Denote it by $B_{00} = [\alpha_{00}, \beta_{00}]$.

Let $k$ be the number of intervals after $B_{00}$ that contains $\beta_{00}$ but not $\alpha_{00}$, $0\le k$. Let them be $B_{10}, B_{20}, \cdots, B_{k0}$ in order. In other words, assuming $B_{i0}= [\alpha_{i0}, \beta_{i0}]$ for all $i$, $1\le i\le k$, we have $\beta_{i0}\le\alpha_{(i+1)0}\lt \beta_{(i+1)0}$ for all $i$, $0\le i\lt k$.

For each $i$, $0\le i\le k$, let us run the usual greedy interval scheduling algorithm starting with $B_{i0}$. (For intervals sorted by ascending end angle used in that greedy algorithm, we can reuse the sorted intervals produced by the first step.) However, instead of running them one by one separately, we will run them in turn. When we find two runs can include the same interval in their respective sets of non-overlapping intervals, stop the run that includes less number of intervals so far, or, in the case when both include the same number of intervals so far, the one that starts earlier. This pruning operation ensures that each interval will be accessed at most a constant number of times. This step of running all scheduling, with a proper implementation, takes $O(n)$ time.

Finally, pick the run that include the most number of non-overlapping intervals. That number is the wanted maximum number.


Here is an implementation in Python, with brief comments. Instead of $2\pi$, parameter perimeter is used to denote the perimeter (by some unit of angle or time). The interval schedules[i][0] in method max_non_overlapping corresponds to $B_{i0}$ above while more_schedules is true.

from collections import deque
from functools import cmp_to_key


def sort_and_reduce(intervals):
    """ Return sorted intervals without any interval contains another """

    # Sort by increasing start. Break ties by decreasing end.
    intervals = sorted(intervals, key=cmp_to_key(lambda x, y: x[0] - y[0] if x[0] != y[0] else y[1] - x[1]))

    result = []
    for cur_interval in intervals:
        # remove intervals that contain `current`
        while result and result[-1][1] >= cur_interval[1]:
            result.pop()
        result.append(cur_interval)
    return result


def max_non_overlapping(perimeter, intervals):
    """ return the maximum number of non-overlapping circular intervals

    Each (circular) interval in `intervals` is a pair `[start, end]`,
    where `0 <= start < perimeter` and `start <= end < start + perimeter`.
    Interval `[start, end]` stands for the set of numbers (angles)
    `0 <= num < perimeter` such that either `start <= num <= end`
    or `start <= num + perimeter <= end`. Two intervals are
    non-overlapping iff their corresponding sets of numbers are disjoint.
    """

    intervals = sort_and_reduce(intervals)

    ans = 0

    # `schedules` is a queue of schedules. Each schedule is a list of
    # non-overlapping intervals in natural order, i.e, ordered by increasing
    # starts as well as by increasing ends since so are `intervals` as they
    # have been sorted and reduced.
    schedules = deque()

    # Are we still building the first intervals of the parallel greedy runs?
    more_schedules = True

    # Invariants for the schedules in `schedules` at the end of each iteration:
    #   1. Every interval appears in most one of the schedules in the queue.
    #   2. The last `end`s of schedules are increasing.
    #   3. Any two adjacent schedules contain the same number of intervals and
    #      the first `start`s in them are increasing, except when the second
    #      schedule contains the the very first interval, at which time the
    #      second schedule contains one more interval than the first schedule.
    for cur_interval in intervals:
        if more_schedules:
            # if `schedules` is empty or the start of `cur_interval` is smaller
            # than or equal to the end of the very first interval.
            if not schedules or cur_interval[0] <= intervals[0][1]:
                schedules.append([cur_interval])
                continue
            else:
                more_schedules = False
        if cur_interval[0] > schedules[0][-1][1]:
            if cur_interval[1] < perimeter:
                while len(schedules) > 1 and cur_interval[0] > schedules[1][-1][1]:
                    # pop schedules[0] since schedules[1] cannot be worse than it.
                    schedules.popleft()
                schedules[0].append(cur_interval)
                # keep schedules sorted by earliest-end first
                schedules.append(schedules.popleft())
            else:
                # a schedule can contain at most one such interval, i.e., an
                # interval whose `end` is at least `perimeter`
                while schedules and cur_interval[0] > schedules[0][-1][1] and \
                        cur_interval[1] < perimeter + schedules[0][0][0]:
                    ans = max(ans, 1 + len(schedules.popleft()))
                while schedules and cur_interval[1] >= perimeter + schedules[0][0][0]:
                    ans = max(ans, len(schedules.popleft()))
                while schedules and cur_interval[0] > schedules[0][-1][1] and \
                        cur_interval[1] < perimeter + schedules[0][0][0]:
                    ans = max(ans, 1 + len(schedules.popleft()))
                if not schedules:
                    break
        # else `cur_interval` cannot be included.

    return max(ans, len(schedules[-1]) if schedules else 0)

    

if __name__ == "__main__":
    perimeter = 16
    intervals = [[5, 13], [4, 8], [3, 16], [1, 14], [10, 19], [2, 9], [7, 18], [11, 12], [15, 17], [6, 20]]
    res = max_non_overlapping(perimeter, intervals)
    print(res)
    # output: 3,  which is the number of intervals in schedule [[4,8], [11,12], [15,17]]
$\endgroup$
4
  • $\begingroup$ Looks promising, but I'm concerned about 2 things: (1) You claim $\beta_{1i} < \alpha_{1(i+1)}$, but this can fail -- two intervals that each overlap $\beta_{11}$ can overlap each other. (It's not clear to me whether this failing to hold upsets things.) (2) The crucial claim seems to be that each interval will be accessed at most a constant number of times, but I have no idea why this should be true -- could you please elaborate? $\endgroup$ Sep 18 '21 at 1:01
  • $\begingroup$ @j_random_hacker Thanks for the comments. (1) Intervals have been sorted. Also no interval contains another one. (2) Indeed, my terse statement did not explain clearly why. Please check my newly-added Python code for more detail. Basically and roughly, each iteration of for cur_interval in intervals: will either add an interval to a unique schedule or pop a schedule out of the the queue. $\endgroup$
    – John L.
    Sep 19 '21 at 14:30
  • $\begingroup$ For (1), in fact, I also need $B_{11}$ is the first remaining interval, which ensures that $\alpha_{11}$ is the smallest start of a given interval. $\endgroup$
    – John L.
    Sep 19 '21 at 15:06
  • $\begingroup$ The full circle as a circular interval cannot be express as $[\alpha, \beta]$, where $0\le\alpha\lt 2\pi$ and $\alpha\le \beta\lt \alpha+2\pi$. However, it is easy to deal with that kind of interval. $\endgroup$
    – John L.
    Sep 19 '21 at 15:59

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.