CODEWITHSUNDEEP
algorithm
Peter
Peter

Reputation: 2759

Insert Interval into a disjoint set of intervals

Given sorted disjoint sets (p,q) where ‘p’ is the start time and ‘q’ is the end time. You will be given one input interval. Insert it in the right place. And return the resulting sorted disjoint sets.

Eg: (1,4);(5,7);(8,10);(13,18)

Input interval – (3,7)
Result : (1,7);(8,10);(13,18)

Input Interval – (1,3)
Result: (1,4);(5,7);(8,10);(13,18)

Input interval – (11,12)
Result: (1,4);(5,7);(8,10);(11,12);(13,18)

Inserting an interval in a sorted list of disjoint intervals , there is no efficient answer here

Upvotes: 1

Views: 1512

Answers (1)

Daniel Brückner
Daniel Brückner

Reputation: 59705

Your question and examples imply non-overlapping intervals. In this case you can just perform a binary search - whether comparison is done by start time or end time does not matter for non-overlapping intervals - and insert the new interval at the position found if not already present.

UPDATE

I missed the merging occurring in the first example. A bad case is inserting a large interval into a long list of short intervals where the long interval overlaps many short intervals. To avoid a linear search for all intervals that have to be merged one could perform two binary searches - one from the left comparing by start time and one from the right comparing by the end time.

Now it is trivial to decide if the interval is present, must be inserted or must be merged with the intervals between the positions found by the two searches. While this is not very complex it is probably very prone to off-by-one errors and requires some testing.

Upvotes: 4

Related Questions