Merge Intervals LeetCode

Key takeaways:
'Merge Intervals' frequently asked in interviews: Top tech companies, including MAANG (Meta, Apple, Amazon, Netflix, Google), often ask this problem to test candidates’ problem-solving abilities, specifically how they manage overlapping ranges and sort data efficiently.
Optimal solution for 'Merge Intervals': The solution first sorts the intervals and then merges the overlapping intervals in a linear scan.
Identify the overlapping intervals: Two intervals overlap if the start of one interval is less than or equal to the end of the previous interval.
Preparation tip: Practice Merge Intervals and similar coding problems to build confidence in interval manipulation, a common topic/theme in coding interviews. These skills help with real-world challenges involving time management, scheduling, and resource allocation.

Discover how mastering the Merge Intervals LeetCode problem can help you stand out in an interview!

The Merge Intervals problem is one of the most commonly asked coding question in technical interviews by top tech companies including MAANG (FAANG)—Meta (Facebook), Apple, Amazon, Netflix, and Google. The interviewers ask the Merge Intervals problem to test the candidate's understanding about working with intervals, which involves sorting and managing overlapping ranges. This is a skill often needed in real-world tasks like scheduling or combining events.

In this Answer, we’ll go over the solution to the Merge Intervals problem in detail to help you improve your interval manipulation skills and prepare to solve this coding problem confidently in your interview. So, let’s begin!

Problem statement

We are given an array of closed intervalsA closed interval includes its start and end points and can be expressed as $x \in [a, b]$ or as $a \leq x \leq b$. However, an open interval does not include either its start or its end point and can be expressed as $x \in (a, b)$ or as $a < x < b$., intervals, where each interval has a start time and an end time. For example, intervals = $[[1,4],[3,6],[7,9]]$ is sorted in terms of start times $1$ , $3$ , and $7$ . Our task is to merge the overlapping intervalsOverlapping intervals have at least one time (start/end) in common. and return a new output array consisting of only the nonoverlapping intervalsNonoverlapping intervals have NO time (start/end) in common..

Example:

Note: In the slides above, if we notice, something is common among all the scenarios of overlapping intervals. If we call ‘a’ the first interval and ‘b’ the second interval, then in all the overlapping scenarios, the start time of the second interval always occurs before the end time of the first interval, that is, b’s start time < a’s end time. Therefore, the first step of solving this problem will be to sort the given intervals by their start times.

In this solution, after sorting the input array, we use the merge intervals pattern with a simple linear scan to merge the overlapping intervals. First, we create an output list and copy the first interval of the input list to it. Next, we traverse the remaining intervals of the input list and check whether any interval overlaps with the interval in the output list. If they overlap, update the interval in the output list. Otherwise, add the current input interval to the output list. Repeat this for all the intervals in the input list. Please note that when we have more than one interval in the output list, we compare the input intervals with the last interval of the output list.

Now, let's go over the algorithm steps:

Sort the input array intervals by the start times of the intervals.
Create an output list and add the first interval from the input list into it.
Iterate through the input list, and examine each interval to determine if it overlaps with the most recent interval in the output list.
1. If there is an overlap, it is merged with the most recent interval in the output list by updating the end time of the latest interval in the output list.
2. If there is no overlap, the current interval is simply appended to the output list.
This process is repeated for all intervals in the input list.

Note: It is important to note that during the merging process, we only compare the current interval with the last one in the output list to decide whether to merge them or add the current interval as a new entry.

Let’s look at the illustration below to see how this algorithm works:

def merge_intervals(intervals):
  
    # Sort the given intervals with respect to their start times
    intervals.sort()
    
    # Initialize the output list with the first interval
    output = []
    output.append([intervals[0][0], intervals[0][1]])
    
    # Iterate over each interval starting from the second one
    for i in range(1, len(intervals)):
      
        # Get the last interval added to the output list
        last_added_interval = output[len(output) - 1]
        
        # Extract the current interval's start and end times
        cur_start = intervals[i][0]
        cur_end = intervals[i][1]
        
        # Get the end time of the last interval added to the output
        prev_end = last_added_interval[1]
        
        # If the current interval overlaps with the last added interval, merge them
        if cur_start <= prev_end:
          
            # Update the end time of the last interval to the maximum of both
            output[-1][1] = max(cur_end, prev_end)
        else:
          
            # If there is no overlap, add the current interval to the output
            output.append([cur_start, cur_end])
            
    # Return the merged list of intervals
    return output
# Driver code
def main():
    
    all_intervals = [
    [[3, 7], [4, 6], [1, 5]],
    [[6, 8], [1, 5], [11, 15], [4, 6]],
    [[11, 15], [3, 7], [10, 12], [6, 8]],
    [[1, 5]],
    [[1, 9], [3, 8], [4, 4]],
    [[1, 2], [8, 8], [3, 4]],
    [[1, 5], [1, 3]],
    [[1, 5], [6, 9]],
    [[0, 0], [1, 18], [1, 3]]
    ]
    for i in range(len(all_intervals)):
        print(i + 1, ". Intervals to merge:\t ", all_intervals[i], sep="")
        output = merge_intervals(all_intervals[i])
        print("   Merged intervals:\t", output)
        print("-"*100)
if __name__ == '__main__':
    main()

Merge Intervals

Code explanation

Let's take a look at what the code above does:

Line 4: Sort the intervals array in place using Python's sort() method.
Lines 7–8: Initialize an empty list output that will store the merged intervals. Then, add the first interval from the intervals list to output. This sets up the initial condition for merging subsequent intervals.
Line 11: Start a for loop from the second interval to the end of the output list. The loop will process each interval to see if it needs to be merged with the last interval in output.
Line 14: Retrieve the last interval added to the output list. This interval will be compared with the current interval to check for overlaps.
Lines 17–18: Extract the start and end points of the current interval from the intervals list.
Line 21: Retrieve the endpoint of the last added interval from the output list.
Line 24: Check if the start of the current interval is less than or equal to the end of the last added interval. This condition tests for an overlap.
Line 27: If there is an overlap, merge the current interval with the last interval in output by updating the end of the last interval to the maximum endpoint between the current and last intervals.
Lines 31: If there is no overlap, add the current interval as a new entry to the output list.
Line 34: Once all intervals have been processed, return the output list containing all merged intervals.

Time complexity

Sorting the intervals take $O(n \log n)$ , where $n$ is the number of intervals in the input array. Iterating through the intervals take $O(n)$ to merge them. Therefore, the overall time complexity is $O(n \log n)$ due to the sorting step.

Space complexity

The space complexity of this solution is $O(n)$ because of the sorting step. The other steps only use constant space.

Coding problems similar to Merge Intervals

The Merge Intervals problem is just one piece of the puzzle that helps you master interval manipulation. There are other coding problems that involve similar concepts of merging, scheduling, and manipulating intervals, providing good practice for improving your skills in this area. Here are a few problems that are similar to the Merge Intervals problem:

Insert Interval: Given a set of intervals and a new interval, insert the new interval into the correct position and merge if necessary.
Employee Free Time: Given a list of employees' schedules, find the free time intervals that all employees have in common.
Meeting Rooms II: Determine the minimum number of meeting rooms required to hold all meetings based on their start and end times.
Interval List Intersections: Given two lists of intervals, find the intersection intervals that exist in both lists.
Maximum Profit in Job Scheduling: Given jobs with start and end times along with their profits, find the maximum profit you can earn by scheduling non-overlapping jobs.
Minimum Number of Arrows to Burst Balloons: Given an array of balloons represented by their start and end points, find the minimum number of arrows needed to burst all the balloons.

On that note, take a look at some other Answers that cover solutions to frequently asked LeetCode problems in detail:

If you think you're done preparing for the technical interview, try attempting Educative's AI-empowered mock interviews. Mock interviews, in general, help you build confidence, improve your problem-solving skills, and identify areas where you can improve before the actual interview. To make it even more helpful for you, Educative's AI-empowered mock interviewer gives an unbiased evaluation.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What is merge intervals?

Merge intervals is a common coding problem that involves taking a collection of intervals and merging any overlapping or contiguous intervals into one. The goal is to simplify the collection by removing redundancies. For example, given the intervals (1,3), (2,6), and (8,10), the merged result would be (1,6) and (8,10). It is frequently asked by tech giants (MAANG/FAANG) in technical interviews. This problem is often used in interviews to test a candidate’s understanding of sorting, iteration, and logical thinking when dealing with overlapping ranges. It has practical applications in scheduling, resource allocation, and event management.

How to solve merge intervals problems?

To solve merge intervals problems, follow these steps:

Sort the Intervals: Begin by sorting the list of intervals based on their starting points. This helps in easily identifying overlapping intervals.
Initialize an Empty List: Create an empty list to hold the merged intervals.
Iterate Through the Sorted Intervals: Loop through each interval in the sorted list:
- I. If the list of merged intervals is empty or the current interval does not overlap with the last merged interval, add it to the merged list.
- II. If there is an overlap (i.e., the start of the current interval is less than or equal to the end of the last merged interval), merge them by updating the end of the last merged interval to be the maximum of its current end and the end of the current interval.
Return the Merged List: After iterating through all intervals, return the list of merged intervals.

How to merge two intervals in Python?

Sort the intervals by their start time.
Check for Overlap: The function checks if the two intervals overlap. If the end of the first interval is less than the start of the second, or the end of the second is less than the start of the first, they do not overlap.
Merge: If they overlap, create a new interval that starts at the minimum of the two starting points and ends at the maximum of the two ending points.
Return the Result: Return either the merged interval or both intervals if there is no overlap.

def merge_intervals(intervals):
    if not intervals:
        return []
    
    # Step 1: Sort the intervals by their start time
    intervals.sort(key=lambda x: x[0])
    
    merged = []
    
    for interval in intervals:
        # Step 2: If the merged list is empty or there's no overlap, add the interval
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            # Step 3: There is overlap, merge the intervals
            merged[-1][1] = max(merged[-1][1], interval[1])
    
    return merged

What do overlapping intervals mean?

Overlapping intervals refer to two or more intervals that share a common range on a number line. In other words, at least one point in the range of one interval falls within the range of another interval.

For example, if you have two intervals:

Interval A: (1, 5)
Interval B: (4, 8)

These intervals overlap because they both include the point 4.

Conditions for Overlapping Intervals:

Intervals overlap if:

The start of one interval is less than or equal to the end of the other interval, and
The end of one interval is greater than or equal to the start of the other interval.

What are real-world examples of merge intervals?

Here are some real-world examples of merge intervals:

Scheduling Meetings: Combining overlapping meeting times to create a consolidated schedule, ensuring that no time slots are double-booked.
Event Management: Merging event timelines when multiple events occur at similar times, such as festivals or conferences, to avoid scheduling conflicts.
Resource Allocation: Optimizing the usage of shared resources (like rooms or equipment) by merging overlapping bookings to maximize availability.
Data Processing: Combining overlapping data ranges in applications like data analysis or network traffic management to simplify datasets.
Calendar Applications: Automatically merging overlapping events in digital calendars to provide users with a clearer view of their schedules.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments