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.


  1. 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\}$.
  2. 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?

  • $\begingroup$ @D.W. I've attempted to clarify the problem a bit and added an example. I realize now it was initially very confusing. $\endgroup$ – alfalfasprout Jan 30 '17 at 22:51
  • $\begingroup$ Thanks for the edit! That was an improvement. However, the problem still doesn't seem fully specified. The interval-overlap relation is not transitive. Suppose we have intervals A,B,C where A,B overlap and B,C overlap but A,C don't overlap. Suppose A is the longest and C is the second-longest. What interval should we return? Just A, or A and C? What about more complex combinations of overlap? The problem spec doesn't feel fleshed out enough to uniquely determine the desired answer, for all possible patterns of overlap. $\endgroup$ – D.W. Jan 30 '17 at 22:53
  • $\begingroup$ @D.W. for some context, the intervals represent phrases in an array of strings. Suppose I have: "the quick brown fox jumped over the lazy dog". I could have phrases "quick brown fox", "brown fox", and "the quick" and "lazy dog" represented by {1,3},{2,3},{0,1}, and {7,8}. I don't want to return a phrase that contains a subphrase. So since "quick brown fox" is a phrase I do not wish to return "brown fox". I also don't with to return phrases that share a word in its position with my longest phrase. So "the quick" and "quick brown fox" overlap. "quick brown fox" is longer so I want that one. $\endgroup$ – alfalfasprout Jan 30 '17 at 23:00
  • $\begingroup$ I'm afraid that context still doesn't answer my question, though -- the problem still doesn't seem fully specified to me. $\endgroup$ – D.W. Jan 31 '17 at 22:11

Your Answer

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

Browse other questions tagged or ask your own question.