Identify

• to find overlapping intervals
• merge intervals if they overlap
• if you’re asked to produce a list with only mutually exclusive intervals
• if you hear the term “overlapping intervals”

Motive

• our goal is to merge the intervals whenever they overlap

Steps

• given two intervals (‘a’ and ‘b’), there will be six different ways the two intervals can relate to each other

• if a.start <= b.start, only 1, 2 and 3 are possible from the above scenarios

• for the two overlapping scenarios 2 and 3, this is how we will merge them:

  

  • we are going to merge them into a new interval c such that: c.start = a.start and c.end = max(a.end, b.end)

Complexity

Time O(n*log(n))

• in the beginning, since we sort the intervals

Space O(n)

• return a list containing all the merged intervals

Common Problems

• [ ] Merge Intervals (medium) Educative.io