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]]
