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

We are given an array of `intervals`

, where each interval has a start time and an end time. The input array is sorted with respect to the start times of each interval. For example, `intervals`

= `[[1,4], [3,6], [7,9]]`

is sorted in terms of start times $1, 3$, and $7$.

Your task is to merge the overlapping intervals and return a new output array consisting of only the nonoverlapping intervals.

**Example:**

Now that we have understood the problem, let’s check our knowledge by solving the MCQ's given below:

Choose the correct option:

1

What is the correct merged interval for the given set of intervals: [[2, 5], [4, 8], [10, 12], [9, 11]]?

A)

[[2, 8], [9, 12]]

B)

[[2, 5], [4, 12]]

C)

[[2, 8], [10, 12]]

D)

[[2, 8], [9, 11], [10, 12]]

Question 1 of 30 attempted

To solve this problem, we need to handle all the six ways in which any two given intervals relate to each other. Before jumping onto the algorithm, let’s review all these ways using the illustration given below:

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:

Let’s have a look at the code for the algorithm we just discussed:

def merge_intervals(intervals):if not intervals:return Noneresult = []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 codedef 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()

**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.

The time complexity of this solution is

The space complexity of this solution is

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS