Merge Intervals LeetCode

The Merge Intervals problem involves efficiently merging overlapping intervals within a list. In employee work shifts, merging overlapping work shifts is essential to create a unified schedule and manage shift overlaps effectively. For example, consider the input intervals: [[8, 12], [11, 15], [14, 18]]. The shift from $8$ to $12$ overlaps with the shift from $11$ to $15$ , so they are merged into a single shift from $8$ to $15$ . This newly merged shift from $8$ to $15$ then overlaps with the shift from $14$ to $18$ , leading to a further merger into a single shift from $8$ to $18$ . By merging these overlapping intervals, a unified shift from $8$ to $18$ is created, helping to manage and optimize work schedules by ensuring continuous coverage without gaps or unnecessary overlaps.

Problem statement

To solve this problem efficiently, we use the straightforward linear scanning approach.
Initially, we establish an output list and populate it with the first interval from the input list.
As we iterate through the input list, we examine each interval to determine if it overlaps with the most recent interval in the output list.
Overlapping intervals are merged by updating the end time of the latest interval in the output list.
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.
It is crucial 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.
This method ensures that the output list contains only non-overlapping intervals by the end of the procedure.

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

def merge_intervals(intervals):
    if not intervals:
        return None
    result = []
    result.append([intervals[0][0], intervals[0][1]])
    for i in range(1, len(intervals)):
        last_added_interval = result[len(result) - 1]
        cur_start = intervals[i][0]
        cur_end = intervals[i][1]
        prev_end = last_added_interval[1]
        
        if cur_start <= prev_end:
            result[-1][1] = max(cur_end, prev_end)
        else:
            result.append([cur_start, cur_end])
    return result
# Driver code
def main():
    
    all_intervals = [
    [[1, 5], [3, 7], [4, 6]],
    [[1, 5], [4, 6], [6, 8], [11, 15]],
    [[3, 7], [6, 8], [10, 12], [11, 15]],
    [[1, 5]],
    [[1, 9], [3, 8], [4, 4]],
    [[1, 2], [3, 4], [8, 8]],
    [[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: ", all_intervals[i], sep="")
        result = merge_intervals(all_intervals[i])
        print("   Merged intervals:\t", result)
        print("-"*100)
if __name__ == '__main__':
    main()

Code explanation

Line 1: Define a function merge_intervals that accepts one parameter, intervals, which is a list of intervals.
Lines 2–3: Check if the list intervals is empty. If it is, return None. This handles the edge case where no intervals are provided.
Line 4: Initialize an empty list result that will store the merged intervals.
Line 5: Add the first interval from the intervals list to result. This sets up the initial condition for merging subsequent intervals.
Line 6: Start a for loop from the second interval to the end of the intervals list. The loop will process each interval to see if it needs to be merged with the last interval in result.
Line 7: Retrieve the last interval added to the result list. This interval will be compared with the current interval to check for overlaps.
Lines 8–9: Extract the start and end points of the current interval from the intervals list.
Line 10: Retrieve the endpoint of the last added interval from the result list.
Line 11: 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 12: If there is an overlap, merge the current interval with the last interval in result by updating the end of the last interval to the maximum endpoint between the current and last intervals.
Lines 13–14: If there is no overlap, add the current interval as a new entry to the result list.
Line 15: Once all intervals have been processed, return the result list containing all merged intervals.

Time complexity

The time complexity of this solution is $O(n)$ , where $n$ is the number of intervals in the input list.

Space complexity

The space complexity of this solution is $O(1)$ because we only use constant space other than the input and output data structures.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Merge Intervals LeetCode

Problem statement

Knowledge test

Algorithm

Coding example

Code explanation

Time complexity

Space complexity