Leetcode is Easy! The Interval Pattern.

How to identify overlapping intervals and merge them.

Introduction

Welcome to the 3rd article in my series, Leetcode is Easy! Today we’ll be covering problems relating to the ‘Interval’ category. I’ll start with an overview, walk through key steps with an example, and then give tips on approaching this problem. As always, I’ll end with a list of questions so you can practice and internalize this patten yourself.

We’ll be following the question Merge Intervals, so open up the link and follow along!

Overview

What is an interval? An Interval is “an intervening period of time”.

Thanks, dictionary.com.

An interval for the purpose of Leetcode and this article is an interval of time, represented by a start and an end. For example, we might be given an interval [1, 10] which represents a start of 1 and end of 10. Some problems assign meaning to these start and end integers. On those that don’t, it’s helpful to assign one yourself and imagine these integers as start/end minutes, hours, days, weeks, etc.

Our problem Merge Intervals follows:

Given a collection of intervals, merge all overlapping intervals.
Input: [[1,3],[5,10],[7,15],[18,30],[22,25]]
Output: [[1,3],[5,15],[18,30]]

So we’re given a collection of intervals as an array. We have individual intervals contained as nested arrays. Each interval has two digits, representing a start and an end. Since this specific problem does not specify what these start/end integers mean, we’ll think of the start and end integers as minutes.

So let’s break it down further.

              s e   s  e   s  e   s   e   s  e
intervals = [[1,3],[5,10],[7,15],[18,30],[22,25]]
               0     1      2       3       4
s = start
e = end
so....
intervals[0] = [1,3]
s = 1
e = 3
"The interval at the 0th index has a start of minute 1 and end of minute 3"
intervals[3] = [18, 30]
s = 18
e = 30
"The interval at the 3rd index has a start of minute 18 and end of minute 30"

We can visualize the interval input as the drawing below (not to scale):

3 Key Steps

Now that we understand what intervals are and how they relate to each other visually, we can go back to our task of merging all overlapping intervals. But before we can begin merging intervals, we need a way to figure out if intervals overlap. Before we figure out if intervals overlap, we need a way to iterate over our intervals input.

Since I love numbered lists, the problem breaks down into the following steps.

1. Iterate over intervals
2. Check if intervals overlap
3. Merge Overlapping intervals

Our pseudocode will look something like this.

def merge(intervals):
    # Iterate over the input intervals     
         # Check two intervals
             # If they overlap, merge them. 
             # If they don't overlap, check the next interval.

To iterate over intervals, we need to introduce a second array to store intervals that we have already checked and potentially merged. We will check overlaps between the last interval of this second array with the current interval in the input. We initialize this second array with the first interval in our input intervals.

Before we go any further, we will need to verify that the input array is sorted. In our example, the array is sorted by start times but this will not always be the case. Clarify with your interviewer and if the intervals are not sorted, we must sort the input first.

def merge(intervals):
    intervals.sort()   
    result = [intervals[0]]
    # Iterate over the input intervals     
    for interval in intervals[1:]: 
        interval_2 = results[-1]
        # Check two intervals, 'interval' and 'interval_2'
             # If they overlap, merge them. 
             # If they don't overlap, check the next interval.

So we’ve figured out step 1, now step 2. How do we check if two intervals overlap?

Well, if we have two intervals, A and B, the relationship between A and B must fall into 1 of 3 cases.

1. Interval A and B do not overlap
2. Interval A and B partially overlap
3. Interval A and B completely overlap

The picture below will help us visualize.

And what do these overlapping cases mean for merging?

1. The intervals do not overlap. We do not have to do any merging.
2. The intervals partially overlap. We merge interval A and interval B into interval C.
3. Interval A completely overlaps interval B. Interval B will be merged into interval A.

So back to identifying if intervals overlap. We can obviously see intervals overlap if the end time of interval A is after the begin time of interval B.

The way I prefer to identify overlaps is to take the maximum starting times and minimum ending times of the two intervals. We then subtract the front maximum from the back minimum to figure out how many minutes these two intervals overlap. Knowing how the duration of the overlap is useful in variation problems which allows me to standardize my approach for all interval problems.

So let’s take max/mins to figure out overlaps.

intervals = [[1,3],[5,10],[7,15],[18,30],[22,25]]
               0      1      2      3        4 
# CASE 1 
interval[0] = [1, 3]
interval[1] = [5, 10]
front = max(1, 5) = 5 
back = min(3, 10) = 3 
back - front = 3 - 5 = -2 
Explanation: The intervals 'overlap' by -2, aka they don't overlap 

# CASE 2 
interval[1] = [5, 10]
interval[2] = [7, 15]
front = max(5, 7) = 7
back = min(10, 15) = 10
back - front = 10 - 7 = 3
Explanation: The intervals overlap by 3 

# CASE 3 
interval[3] = [18, 30]
interval[4] = [22, 25] 

front = max(18, 22) = 22 
back = min(30, 25) = 25
back - front = 25 - 22 = 3 
Explanation: The intervals overlap by 3

In code, we can define a helper function that checks two intervals overlap as the following:

def do_overlap(interval_1, interval_2):
    front = max(interval_1[0], interval_2[0])
    back = min(interval_1[1], interval_2[1])
    return back - front >= 0 

This function will return True if the two intervals overlap and False if they do not. Remember, intervals overlap if the ‘front — back’ is greater than or equal to 0. In this problem, we assume that intervals that touch are overlapping (eg: [1,5] and [5,10] should be merged into [1, 10]).

Let’s include our helper function inside our code.

def merge(intervals):
    result = [intervals[0]]
    # Iterate over the input intervals     
    for interval in intervals[1:]: 
        interval_2 = result[-1]
         # If they overlap, merge them.             
         if do_overlap(interval, interval_2):
             # Merge
         # If they don't overlap, check the next interval.
         else:
             result.append(interval)
def do_overlap(interval_1, interval_2):
    front = max(interval_1[0], interval_2[0])
    back = min(interval_1[1], interval_2[1])
    return back - front >= 0

So we know how to iterate over our intervals and check the current interval iteration with the last interval in our result array. We’ve written our helper function that returns True if the intervals do overlap, which allows us to enter body of the if statement and #merge. If they do not overlap, we append the current interval to the results array and continue checking.

So how do we merge?

intervals = [[1,3],[5,10],[7,15],[18,30],[22,25]]
Partial Overlap
 [5     10] 
     [7       15] 
becomes...
[5            15]
Complete Overlap
[18                30]
      [22   25]
becomes...
[18                30]

The newly merged interval will be the minimum of the front and the maximum of the end. We set the last interval of the result array to this newly merged interval.

def merge(intervals):
    intervals.sort()   
    result = [intervals[0]]
    # Iterate over the input intervals     
    for interval in intervals[1:]: 
        interval_2 = result[-1]
        # If they overlap, merge them.             
        if do_overlap(interval, interval_2):
            merged_front = min(interval[0], interval_2[0])
            merged_back = max(interval[1], interval_2[1])
            result[-1] = [merged_front, merged_back]
        # If they don't overlap, check the next interval.
        else:
            result.append(interval)
    return result
def do_overlap(interval_1, interval_2):
    front = max(interval_1[0], interval_2[0])
    back = min(interval_1[1], interval_2[1])
    return back - front >= 0

Once we have iterated over and checked all intervals in the input array, we return the results array.

High-Level Strategy

As recap, we broke our problem down into the following steps:

1. Iterate over intervals
2. Check if intervals overlap
3. Merge Overlapping intervals

Key points to remember for each step are:

1. Introduce a Result Array: Introduce a second array to store processed intervals and use this result array to compare against the input intervals array.
2. How to Check Overlaps: The duration of the overlap can be calculated by back minus front, where ‘front’ is the maximum of both starting times and ‘back’ is the minimum of both ending times. If the intervals do not overlap, this duration will be negative. Confirm with the interviewer that ‘touching’ intervals (duration of overlap = 0) are considered overlapping.
3. Merge Intervals: If we identify an overlap, the new merged range will be the minimum of starting times and maximum of ending times.

Last but not least, remember that the input intervals must be sorted by start time for this process to work.

Practice

• Merge Intervals
• Meeting Rooms
• Meeting Rooms II
• Interval List Intersection
• Insert Intervals