TIC
The Interns Company

Merge Intervals

MediumAcceptance: 43.5%
ArraySorting

Problem Statement

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.

Constraints:

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 10^4

Input Format:

  • An array of intervals where intervals[i] = [starti, endi]

Output Format:

  • An array of the non-overlapping intervals that cover all the intervals in the input

Examples:

Example 1:

Input:

intervals = [[1,3],[2,6],[8,10],[15,18]]

Output:

[[1,6],[8,10],[15,18]]

Explanation:

Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input:

intervals = [[1,4],[4,5]]

Output:

[[1,5]]

Explanation:

Intervals [1,4] and [4,5] are considered overlapping since they share an endpoint.

Example 3:

Input:

intervals = [[1,4],[0,4]]

Output:

[[0,4]]

Explanation:

Interval [0,4] covers interval [1,4], so they are merged.

Solutions

Sort and Merge

Time: O(n log n) due to sorting
Space: O(n) for the result array

Sort the intervals by start time, then iterate through the intervals, merging overlapping ones.

Line Sweep Algorithm

Time: O(n log n) due to sorting
Space: O(n) for the result array

Keep track of the start and end points separately, then perform a line sweep to determine the merged intervals.

Algorithm Walkthrough

Example input:

Step-by-step execution:

  1. intervals = [[1,3],[2,6],[8,10],[15,18]]
  2. Sort by start time: [[1,3],[2,6],[8,10],[15,18]]
  3. Initialize result = [[1,3]]
  4. i=1: intervals[1] = [2,6]
  5. Last merged interval = [1,3]
  6. Since 2 <= 3, there is an overlap, merge to [1,6]
  7. result = [[1,6]]
  8. i=2: intervals[2] = [8,10]
  9. Last merged interval = [1,6]
  10. Since 8 > 6, no overlap, add to result
  11. result = [[1,6],[8,10]]
  12. i=3: intervals[3] = [15,18]
  13. Last merged interval = [8,10]
  14. Since 15 > 10, no overlap, add to result
  15. result = [[1,6],[8,10],[15,18]]
  16. Return result = [[1,6],[8,10],[15,18]]

Hints

Hint 1
Sort the intervals based on the start time.
Hint 2
After sorting, merge overlapping intervals by comparing the end of the current interval with the start of the next interval.
Hint 3
Keep track of the merged intervals as you go through the sorted array.

Video Tutorial

Merge Intervals - Sort and Merge Approach

YouTube•Learn the Merge Intervals solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the intervals on a number line and how they merge as the algorithm progresses.

Key visualization elements:

  • current interval
  • merged interval
  • result after each step

Similar Questions

Insert Interval

Medium

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith 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.

Meeting Rooms

Easy

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings. In other words, check if there are any overlapping intervals.

Meeting Rooms II

Medium

Given an array of meeting time intervals where intervals[i] = [starti, endi], find the minimum number of conference rooms required to hold all meetings.

Asked By

GoogleFacebookMicrosoftAmazonLinkedInAppleBloomberg

Implementation Notes

This is a classic interval problem. The key insight is to sort the intervals first, which makes the merging process much simpler.