Merge Intervals

"Merge Intervals" and related problems focus on arrays of intervals. Here, each interval is an array of length two consisting of a start time and an end time.

An example of such an interval list: [[5,8], [3,5], [1,2], [7,10]

To solve these problems, we iterate through pairs of intervals after sorting our interval list. For each pair, we decide if and how to merge the pairs based on how they "line up". In general, interval pairs can "line up" in the following ways:

Now consider the following problem:

Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

To solve this problem, we can start by sorting the intervals by start time, then iterating through adjacent pairs of intervals from the start of the interval array all the way to the end. Before we begin iterating through pairs we also create a new List/Auto-resizing array ans to store our final answer to return.

For each pair we do one of two things:

• If they overlap: merge the pair of intervals, and replace the second interval in the pair with the merged interval
• If they do NOT overlap: append the first Interval in the pair at the end of ans.

Notice that since we sorted the intervals by start time, we only have to divide each interval pair into cases where the first interval’s start time is less than (or equal to) the second interval’s start time.

Let’s see how this works on an example input: [[5,8], [3,5], [1,2], [7,10]]

• first sort by start time: [[1,2], [3,5], [5,8], [7,10]]
• iterate through pairs:
  • pair: [1,2] and [3,5] → no overlap → do not merge → append [1,2] to answer so far input array = [[1,2], [3,5], [5,8], [7,10]] answer so far = [[1,2]]
  • pair: [3,5] and [5,8] → overlap → merge input array = [[1,2], [3,5], [3,8], [7,10]] answer so far = [[1,2]]
  • pair: [3,8] and [7,10] → overlap → merge input array = [[1,2], [3,5], [3,8], [3,10]] answer so far = [[1,2]]
  • always add last interval [3,10] when we reach the end of the input array return answer so far = [[1,2],[3,10]]
• And we are done!!!

Problems for this Week

(medium) merge-intervals

Given an array of intervalswhere intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

(medium) insert-interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the $i^\text{th}$ interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion.

(medium) interval-list-intersections

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.