Sorting Applications: Interval Merging and Meeting Rooms

Merge Intervals (LeetCode 56)

Strategy: Sort internal ranges by their start times, then merge overlapping neighbors.

public int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;
    
    // Sort by start point ascending
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> result = new ArrayList<>();
    
    for (int[] current : intervals) {
        // If result is empty or current doesn't overlap with previous, add it
        if (result.isEmpty() || result.getLast()[1] < current[0]) {
            result.add(current);
        } else {
            // Overlap detected: expand the previous interval's end
            result.getLast()[1] = Math.max(result.getLast()[1], current[1]);
        }
    }
    return result.toArray(new int[0][]);
}

Complexity: O(N log N) time due to sorting.

Insert Interval (LeetCode 57)

Since the input list is already sorted, we avoid full sorting and process in three distinct phases: Left non-overlapping, Merged overlap, and Right non-overlapping.

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0, n = intervals.length;
    
    // 1. Add all intervals that end BEFORE the newInterval starts
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i++]);
    }
    
    // 2. Merge all intervals that overlap with newInterval
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.add(newInterval);
    
    // 3. Add remaining intervals that start AFTER newInterval ends
    while (i < n) {
        result.add(intervals[i++]);
    }
    
    return result.toArray(new int[0][]);
}

Meeting Rooms I (LeetCode 252)

Determine if a person can attend all meetings (i.e., NO conflicts).

public boolean canAttendMeetings(int[][] intervals) {
    // Conflict exists if any i starts before i-1 ends
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < intervals[i-1][1]) return false;
    }
    return true;
}

Meeting Rooms II (LeetCode 253)

Find the minimum number of conference rooms required for all meetings.

public int minMeetingRooms(int[][] intervals) {
    if (intervals == null || intervals.length == 0) return 0;
    
    // Sort meetings by start time
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    
    // Min-Heap to track the earliest available time for each room
    PriorityQueue<Integer> allocator = new PriorityQueue<>();
    
    for (int[] meeting : intervals) {
        // If a room becomes free before the meeting starts, reuse it
        if (!allocator.isEmpty() && allocator.peek() <= meeting[0]) {
            allocator.poll();
        }
        // Allocate a room (either reuse or brand new)
        allocator.offer(meeting[1]);
    }
    return allocator.size();
}

Non-overlapping Intervals (LeetCode 435)

Maximize the number of successfully held meetings $\rightarrow$ Greedily pick the one that ends the earliest.

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) return 0;
    
    // Sort by end time ascending (Greedy strategy)
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    
    int removals = 0, currentEnd = Integer.MIN_VALUE;
    for (int[] interval : intervals) {
        if (interval[0] >= currentEnd) {
            currentEnd = interval[1];
        } else {
            removals++; // Conflict: must remove current interval
        }
    }
    return removals;
}

Summary Selection Table