3
$\begingroup$

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\}]$

  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?

$\endgroup$
  • $\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.