0
$\begingroup$

I have different time intervals (contains partial or full overlaps). I provided the sample input and output so that it would be easy to understand.

Sample Input-1: [1-5, 2-3, 3-5, 3-5, 3-6]

Sample Output-1: [(1-2):1, (2-3):2, (3-5):4, (5-6):1]

The above output informs that, for the interval (1-2), there is only one interval (among given inputs) that overlaps. for the interval (2-3), both inputs 1-5 and 2-3 overlap. and so on.

I did a search and found that an interval tree (with slight modifications) could be the best match to store and produce this output. I am here to hear the other's opinion on which could be the more suitable data structure for my use case.

PS:

I don't wish to update/read/delete the tree. Just insert the interval and flat that tree similar to the sample output.

Sample Input-2: [1-2, 3-4, 5-6]

Sample Output-2: [(1-2):1, (3-4):1, (5-6):1]

Sample Input-3: [1-3, 3-4, 5-6]

Sample Output-3: [(1-3):1, (3-4):1, (5-6):1]

Sample Input-4: [1-4, 3-4, 5-6]

Sample Output-4: [(1-2):1, (3-4):2, (5-6):1]

$\endgroup$
5
  • 1
    $\begingroup$ Welcome to CS.SE! Please edit your question to provide a clear statement of the problem you are trying to solve. A good way is to specify the inputs and the desired output in general. A single example does not constitute a clear problem specification. Please don't ask about "best", because that is a matter of opinion -- instead, please identify what your criteria are (asymptotic running time?) or how you will evaluate answers. Requests for opinions are off-topic here: see our help center. $\endgroup$
    – D.W.
    Sep 2 at 22:47
  • $\begingroup$ Please add to your question: Is the data structure to support solving set problems (for a set of query intervals, report the respective numbers of overlapping intervals in the multiset kept)? Does it need to support answering individual queries fast? Does the multiset change between queries - intervals added, changed (one limit) or deleted? $\endgroup$
    – greybeard
    Sep 3 at 4:46
  • $\begingroup$ @greybeard I have added the clarification in my question. $\endgroup$ Sep 3 at 12:44
  • $\begingroup$ @D.W. I added clarity to my question. Please let me know if you still facing difficulty in understanding the question. $\endgroup$ Sep 3 at 15:22
  • $\begingroup$ I'm still hoping you will provide a general specification, not a list of example input-output pairs. I don't see a question in the post. We are a question-and-answer site, so we require you to articulate a specific question. Your title still refers to "best", but there is no explanation what you mean by that or how you will evaluate answers, and the body still requests opinions, which is not what this site is for. $\endgroup$
    – D.W.
    Sep 3 at 17:26

2 Answers 2

1
$\begingroup$

Copy all interval endpoints to a single array, together with a start/end flag and sort on increasing times.

Sample Input-1: [1-5, 2-3, 3-5, 3-5, 3-6]

Sorted list: [1+, 2+, 3-, 3+, 3+, 3+, 5-, 5-, 5-, 6-]

Now by traversing the sorted list, you directly know the numbers of overlapping intervals: [<1:0,1:1,2:2,3:4,5:1,>=6:0] (equal values have been merged).

$\endgroup$
2
$\begingroup$

You can compute the desired output in time $O(n \log n)$, where $n$ is the number of intervals, without any advanced data structure.

For the sake of simplicity suppose that there are no intervals of length $0$ and that the set of all endpoints of the intervals is $\{1,2,\dots,k\}$ with $k=O(n)$. This can be guaranteed w.l.o.g. by performing coordinate compression (sort the times, remove the duplicates, and replace each occurrence of a time $t$ with the rank $r_t$ of $t$. This rank $r_t$ also allows you to recover the original time once you are done) which ensures $k \le 2n$.

Sort the intervals twice, once by their starting time and once by the ending time (this requires time $O(n \log n)$). For each $i \in \{1,\dots,k\}$ let $B_i$ (resp. $E_i$) be the number of intervals that begin (resp. end) not later than point $i$. All $B_i$ and $E_i$ can be found in time $O(n)$ by a linear scan of the sorted intervals.

The output consists of one interval $(i, i+1)$ for each $i \in \{1,\dots,k-1\}$ . The number of input intervals that intersect $(i, i+1)$ is exactly the number of intervals that are "alive" at time $i$, i.e., that begin at some time $\le i$ and end at some time $> i$. Those are exactly $B_i - E_i$.

If the times are integers and their absolute value is upper bounded by $n^k$, for some constant $k$, the sorting step can be performed using the Radix Sort algorithm. This lowers the overall running time to $O(n)$, which is optimal.

$\endgroup$
8
  • $\begingroup$ Could you spell that out, e.g., for input [1-3, 4-5, 6-8] and "query/output intervals" [(2-7):?, (4-5):?]? $\endgroup$
    – greybeard
    Sep 3 at 13:37
  • $\begingroup$ @steven, IMO, I think this approach really works. Relatively this approach works slower than the interval tree, but it greatly increases the simplicity. I like to give some thought and give time to others' opinions and suggestions before accepting this answer. Thanks for showing this pointer. $\endgroup$ Sep 3 at 13:53
  • $\begingroup$ @greybeard As I understand, the desired output for those input intervals would be [(1-3): 1, (3-4): 0, (4,5): 1, (5-6):0, (6-8): 1]. After coordinate compression the input becomes: [1-2, 3-4, 5-6]. The values $B_1, \dots, B_6$ are 1, 1, 2, 2, 3, 3. The values $E_1, \dots, E_6$ are 0, 1, 1, 2, 2, 3. The output is [(1-2):1, (2-3): 0, (3-4): 1, (4-5): 0, (5-6): 1]. Undoing coordinate compression we obtain [ (1-3): 1, (3-4): 0, (4,5): 1, (5-6):0, (6-8): 1]. $\endgroup$
    – Steven
    Sep 3 at 13:57
  • $\begingroup$ "A single example does not constitute a clear problem specification." - I expect the desired output to be [(2-7):3, (4-5):1]. $\endgroup$
    – greybeard
    Sep 3 at 14:02
  • $\begingroup$ @KarthikNedunchezhiyan. I'm surprised that (a proper implementation) of this would be slower than interval trees. The answer is described in multiple steps for the sake of clarity, but everything can be implemented by sorting the multi-set of the interval endpoints once and performing a single linear scan. $\endgroup$
    – Steven
    Sep 3 at 14:03

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.