3.43 Merge and Sort Intervals with Arrays

3.43.1 Problem Metadata

  • Platform: Other
  • Problem ID:
  • Difficulty: Medium
  • URL: NA
  • Tags:
  • Techniques: Sorting, Array, Intervals

3.43.2 Description

Note: This problem is nearly identical to Merge Intervals (LeetCode #56). The core algorithm and approach are the same.

Given an array of intervals [startTime, endTime], merge all overlapping intervals and return a sorted array of non-overlapping intervals.

Key Details: - Intervals may be provided in any order - Duplicates and fully contained intervals are allowed - Return intervals sorted by increasing start time

3.43.3 Examples

Example 1:

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Explanation:
- Step 1: Sort intervals by start time (already sorted)
- Step 2: Initialize merged lc-list with first interval [1,3]
- Step 3: Compare [2,6] with last merged [1,3]. They overlap (2 ≤ 3), so merge into [1,6]
- Step 4: Compare [8,10] with last merged [1,6]. No overlap (8 > 6), append [8,10]
- Step 5: Compare [15,18] with last merged [8,10]. No overlap (15 > 10), append [15,18]
Result: [[1,6],[8,10],[15,18]]

Example 2:

Input: intervals = [[5, 10]]
Output: [[5, 10]]
Explanation: Only one interval, return as-is

Example 3:

Input: intervals = []
Output: []
Explanation: Empty input returns empty output

3.43.4 Input Format

  • First line: integer n denoting the number of intervals
  • Second line: integer 2 denoting the length of individual interval array
  • Next n lines: two space-separated integers startTime and endTime

Example:

4
2
1 3
2 6
8 10
15 18

3.43.5 Constraints

  • \(0 \le\) intervals.length \(\le 100000\)
  • intervals[i].length == 2 for all \(0 \le i <\) intervals.length
  • \(0 \le\) intervals[i][0] \(<\) intervals[i][1] \(\le 10^9\) for all \(0 \le i <\) intervals.length

3.43.6 Solution

3.43.6.1 Walkthrough

Sort intervals by start time, then sweep through the list and merge any interval that overlaps the current merged tail. When there is no overlap, append the current interval as a new block.

Cross-Reference: See Merge Intervals for the complete solution walkthrough, analysis, and implementation.

This problem uses the identical algorithm as LeetCode #56:

  1. Sort intervals by start time
  2. Merge overlapping intervals by comparing current.start with last.end
  3. Return the merged result sorted by start time

3.43.7 Solution

If you prefer working with arrays or the problem accepts int[][] input:

3.43.7.1 Code - Java

import java.util.*;

public class Solution {
    public static int[][] mergeIntervals(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][0];
        }

        // Sort by start time
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        List<int[]> merged = new ArrayList<>();
        merged.add(intervals[0].clone());

        for (int i = 1; i < intervals.length; i++) {
            int[] current = intervals[i];
            int[] last = merged.get(merged.size() - 1);

            // Check for overlap (current.start <= last.end)
            if (current[0] <= last[1]) {
                // Merge by extending the end time
                last[1] = Math.max(last[1], current[1]);
            } else {
                // No overlap, add new interval
                merged.add(current.clone());
            }
        }

        return merged.toArray(new int[merged.size()][]);
    }
}