Practice/Amazon/Leetcode 56. Merge Intervals

Leetcode 56. Merge Intervals

CodingMust

Problem

You are building a meeting room scheduling system. Given a collection of time intervals where each interval is represented as [start, end], consolidate all overlapping or adjacent intervals into the minimum number of non-overlapping intervals.

Two intervals overlap if one starts before or exactly when the other ends. For example, [1,3] and [2,6] overlap, and [1,4] and [4,5] are adjacent (touching at point 4) and should be merged.

Return the consolidated list of intervals.

Requirements

1. Merge all overlapping intervals into single intervals
2. Merge adjacent intervals that touch at their endpoints
3. Return the minimum number of intervals needed to cover all the original intervals
4. The output intervals should be sorted by their start times
5. Each interval is guaranteed to have start <= end

Constraints

• 1 ≤= intervals.length ≤= 10,000
• intervals[i].length == 2
• 0 ≤= start ≤= end ≤= 10,000
• The input may be unsorted

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 (they touch at 4).

Example 3:

Input: intervals = [[1,10],[2,3],[4,5],[6,7],[8,9]] Output: [[1,10]] Explanation: All smaller intervals are contained within [1,10], so they all merge.