Pular para o conteúdo principal

Merge Intervals

Given a list of interval objects, merge all overlapping intervals and return the result.

Note: An interval object is a simple object that contains a start time and end time. Two intervals overlap if the start of one is less than or equal to the end of the other.

Example(s)​

Example 1:

Input: intervals = [[1, 3], [1, 8]]
Output: [[1, 8]]
Explanation:
Intervals [1, 3] and [1, 8] overlap, so they merge into [1, 8].

Example 2:

Input: intervals = [[1, 2], [2, 6], [7, 10]]
Output: [[1, 6], [7, 10]]
Explanation:
Intervals [1, 2] and [2, 6] overlap (2 touches 2), so they merge into [1, 6].
Interval [7, 10] doesn't overlap with [1, 6], so it remains separate.

Example 3:

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]
Explanation:
Intervals [1, 4] and [4, 5] overlap (4 touches 4), so they merge into [1, 5].

Example 4:

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Explanation:
[1, 3] and [2, 6] overlap → merge to [1, 6]
[8, 10] and [15, 18] don't overlap with others → remain separate

Solution​

The solution uses sorting and greedy merging:

  1. Sort intervals: Sort by start time (and end time as tiebreaker)
  2. Iterate through sorted intervals: Process each interval
  3. Check overlap: If current interval overlaps with the last merged interval, merge them
  4. Merge logic: Two intervals [a, b] and [c, d] overlap if a <= d and c <= b
  5. Add new interval: If no overlap, add current interval as a new interval

JavaScript Solution

/**
* Merge overlapping intervals
* @param {number[][]} intervals - Array of [start, end] intervals
* @return {number[][]} - Merged intervals
*/
function merge(intervals) {
// Edge case: empty or single interval
if (intervals.length <= 1) {
  return intervals;
}

// Sort intervals by start time (and end time as tiebreaker)
intervals.sort((a, b) => {
  if (a[0] !== b[0]) {
    return a[0] - b[0]; // Sort by start time
  }
  return a[1] - b[1]; // If start times equal, sort by end time
});

const merged = [];
merged.push(intervals[0]); // Add first interval

// Iterate through remaining intervals
for (let i = 1; i < intervals.length; i++) {
  const current = intervals[i];
  const lastMerged = merged[merged.length - 1];
  
  // Check if current interval overlaps with last merged interval
  // Overlap if: current.start <= lastMerged.end
  if (current[0] <= lastMerged[1]) {
    // Merge: update end time to maximum of both
    lastMerged[1] = Math.max(lastMerged[1], current[1]);
  } else {
    // No overlap, add as new interval
    merged.push(current);
  }
}

return merged;
}

// Test cases
console.log('Example 1:', merge([[1, 3], [1, 8]])); 
// [[1, 8]]

console.log('Example 2:', merge([[1, 2], [2, 6], [7, 10]])); 
// [[1, 6], [7, 10]]

console.log('Example 3:', merge([[1, 4], [4, 5]])); 
// [[1, 5]]

console.log('Example 4:', merge([[1, 3], [2, 6], [8, 10], [15, 18]])); 
// [[1, 6], [8, 10], [15, 18]]

console.log('Test 5:', merge([[1, 4], [0, 4]])); 
// [[0, 4]]

console.log('Test 6:', merge([[1, 4], [0, 1]])); 
// [[0, 4]]
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (More Explicit Overlap Check)​

Here's a version with a more explicit overlap check:

/**
 * Alternative with explicit overlap check
 */
function mergeIntervals(intervals) {
  if (intervals.length <= 1) return intervals;
  
  // Sort by start time
  intervals.sort((a, b) => a[0] - b[0]);
  
  const result = [intervals[0]];
  
  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const last = result[result.length - 1];
    
    // Explicit overlap check: intervals overlap if
    // current.start <= last.end AND last.start <= current.end
    if (current[0] <= last[1] && last[0] <= current[1]) {
      // Merge: take minimum start and maximum end
      last[0] = Math.min(last[0], current[0]);
      last[1] = Math.max(last[1], current[1]);
    } else {
      // No overlap
      result.push(current);
    }
  }
  
  return result;
}

Complexity​

  • Time Complexity: O(n log n) - Where n is the number of intervals. Sorting takes O(n log n), and merging takes O(n).
  • Space Complexity: O(n) - For the result array. If we modify in-place, it could be O(1), but typically we return a new array.

Approach​

The solution uses sorting and greedy merging:

  1. Sort intervals: Sort by start time (and end time as tiebreaker)

    • This ensures that overlapping intervals are adjacent after sorting

  2. Initialize result: Add the first interval to the result

  3. Iterate and merge: For each subsequent interval:

    • Check overlap: If current.start <= lastMerged.end, they overlap
    • Merge: Update lastMerged.end = max(lastMerged.end, current.end)
    • No overlap: Add current interval as a new interval

  4. Return result: Return the merged intervals

Key Insights​

  • Sorting is crucial: After sorting by start time, we only need to check adjacent intervals
  • Greedy approach: Merge intervals as we encounter them
  • Overlap condition: Two intervals [a, b] and [c, d] overlap if a <= d and c <= b
  • After sorting: We only need to check if current.start <= lastMerged.end
  • Merging: Take the minimum start and maximum end of overlapping intervals

Step-by-Step Example​

Let's trace through Example 2: intervals = [[1, 2], [2, 6], [7, 10]]

Step 1: Sort intervals (already sorted)
  intervals = [[1, 2], [2, 6], [7, 10]]

Step 2: Initialize result
  result = [[1, 2]]

Step 3: Process [2, 6]
  current = [2, 6]
  lastMerged = [1, 2]
  Check: current[0] (2) <= lastMerged[1] (2)? Yes → overlap
  Merge: lastMerged[1] = max(2, 6) = 6
  result = [[1, 6]]

Step 4: Process [7, 10]
  current = [7, 10]
  lastMerged = [1, 6]
  Check: current[0] (7) <= lastMerged[1] (6)? No → no overlap
  Add: result.append([7, 10])
  result = [[1, 6], [7, 10]]

Final: [[1, 6], [7, 10]]

Visual Representation​

Intervals:     After sorting:    Merged:
[1, 2]         [1, 2]           [1, 6]──────┐
[2, 6]    →    [2, 6]    →      [7, 10]────┘
[7, 10]        [7, 10]

[1, 2] and [2, 6] overlap → merge to [1, 6]
[7, 10] doesn't overlap → keep separate

Overlap Detection​

Two intervals [a, b] and [c, d] overlap if:

  • a <= d AND c <= b

After sorting by start time, if we have [a, b] followed by [c, d]:

  • We know a <= c (because sorted)
  • So we only need to check c <= b (which is current.start <= lastMerged.end)

Edge Cases​

  • Empty array: Return []
  • Single interval: Return the interval as-is
  • No overlaps: Return all intervals unchanged
  • All overlap: Merge into one interval
  • Nested intervals: [1, 10] and [2, 5] → merge to [1, 10]
  • Touching intervals: [1, 2] and [2, 3] → merge to [1, 3] (touching counts as overlap)

Important Notes​

  • Touching intervals merge: [1, 2] and [2, 3] are considered overlapping
  • Sorting is necessary: Without sorting, we might miss overlaps
  • In-place vs new array: Can modify input or return new array
  • Stable sort: Maintains relative order of non-overlapping intervals
  • Insert Interval: Insert a new interval into sorted non-overlapping intervals
  • Non-overlapping Intervals: Remove minimum intervals to make non-overlapping
  • Meeting Rooms: Check if intervals overlap (boolean)
  • Meeting Rooms II: Find minimum rooms needed (different problem)
  • Interval List Intersections: Find intersections of two interval lists

Takeaways​

  • Sorting first simplifies the merging logic
  • Greedy approach works optimally for this problem
  • Overlap check is simple after sorting: current.start <= last.end
  • Touching intervals are considered overlapping
  • O(n log n) is optimal due to sorting requirement