Suppose we have the following array of pairs representing start and end indices within an array. Think of them as an interval. I'll be using this term from now on.$[\left\{1,3\right\},\left\{4,9\right\},\left\{2,11\right\},\left\{8,14\right\},\left\{16,21\right\}]$I want to yield all intervals which contain no other interval and do not overlap with another interval. As an example, $\left\{2,11\right\}$ contains $\left\{4,9\right\}$ (it is a superset). So we would return $\left\{2,11\right\}$ but not $\left\{4,9\right\}$.If one or more intervals partially overlap, we yield only one of these intervals. We use the following rules to determine which one:If one of the intervals (among those overlapping) has the largest length, we return that one.If they all have the same length, we return the interval with the lowest starting index.So for this example, we would yield:$[\left\{2,11\right\},\left\{16,21\right\}]$. Why? $\left\{4,9\right\}$ is a subset of $\left\{2,11\right\}$ so it's eliminated. $\left\{1,3\right\}$, $\left\{2,11\right\}$, and $\left\{8,14\right\}$ contain partial overlaps with one another. But $\left\{2,11\right\}$ has the largest length among those intervals so we yield that one. $\left\{16,21\right\}$ overlaps with no other interval partially or in full so it is yielded as well.Is there a way to achieve a better than $O(n \log n )$ solution to this problem?
Given An Array of Intervals, Find the Supersets
algorithms;arrays