Pattern 05: Merge Intervals

0. The Template (Copy-Paste Skeleton)

Sort first, then a single linear sweep. Sort by start to merge; sort by end for greedy “max non-overlapping”; use a min-heap of end times for room/resource counting.

// TEMPLATE A — MERGE OVERLAPPING INTERVALS (LC 56)
int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));   // by START
    List<int[]> out = new ArrayList<>();

    for (int[] cur : intervals) {
        int[] last = out.isEmpty() ? null : out.get(out.size() - 1);
        if (last != null && cur[0] <= last[1]) {          // OVERLAP (use < if touching ≠ merging)
            last[1] = Math.max(last[1], cur[1]);          // extend in place — cur may be nested
        } else {
            out.add(new int[]{cur[0], cur[1]});           // disjoint → start a new interval
        }
    }
    return out.toArray(new int[0][]);
}

// TEMPLATE B — MIN ROOMS / MAX CONCURRENT (LC 253) — min-heap of END times
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
PriorityQueue<Integer> endTimes = new PriorityQueue<>();   // earliest-finishing room on top
for (int[] iv : intervals) {
    if (!endTimes.isEmpty() && endTimes.peek() <= iv[0]) endTimes.poll();  // a room freed up
    endTimes.offer(iv[1]);
}
return endTimes.size();       // peak concurrency == rooms needed

// TEMPLATE C — SWEEP LINE (same answer, no heap)
int[] starts = ..., ends = ...;   Arrays.sort(starts); Arrays.sort(ends);
int rooms = 0, best = 0, e = 0;
for (int s = 0; s < starts.length; s++) {
    while (e < ends.length && ends[e] <= starts[s]) { rooms--; e++; }
    rooms++; best = Math.max(best, rooms);
}

// TEMPLATE D — MAX NON-OVERLAPPING / MIN REMOVALS (LC 435) — sort by END, greedy
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));   // by END
int lastEnd = Integer.MIN_VALUE, kept = 0;
for (int[] iv : intervals) if (iv[0] >= lastEnd) { kept++; lastEnd = iv[1]; }
return intervals.length - kept;

The decision table

Question	Sort by	Structure
Merge overlapping ranges	start	running last interval
Insert one interval into a sorted list	already sorted	3 phases: before / merge / after
Minimum meeting rooms, max concurrency	start	min-heap of end times
Max intervals you can keep (min removals)	end	greedy, track lastEnd
Intersection of two interval lists	both sorted	two pointers, max(start) vs min(end)

The two overlap tests — get these exactly right

• Overlap: a.start <= b.end && b.start <= a.end
• Intersection (if any): [max(a.start, b.start), min(a.end, b.end)], valid iff lo <= hi
• Integer.compare(a[0], b[0]), never a[0] - b[0] — subtraction overflows.

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• “Overlapping intervals” or “merge ranges”
• “Meeting rooms” or “schedule conflicts”
• “Insert an interval into a list of non-overlapping intervals”
• Input is a list of [start, end] pairs
• “Find free time” between intervals

The Algorithm (Pseudocode)

sort intervals by start time

merged = [intervals[0]]

for each interval in intervals[1:]:
    lastMerged = merged.last()
    if interval.start <= lastMerged.end:
        lastMerged.end = max(lastMerged.end, interval.end)
    else:
        merged.add(interval)

return merged

The ‘Trick’ to Know

• Overlap condition: Two intervals [a, b] and [c, d] overlap if and only if a <= d && c <= b. But after sorting by start, you only need to check interval.start <= lastMerged.end.
• Edge: [1,5] and [5,8] are considered overlapping (touching endpoints).

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Merge Intervals - LC 56

Brute Force: O(n^2)

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> result = new ArrayList<>(Arrays.asList(intervals));
        boolean merged = true;

        while (merged) {
            merged = false;
            for (int i = 0; i < result.size(); i++) {
                for (int j = i + 1; j < result.size(); j++) {
                    if (result.get(i)[0] <= result.get(j)[1] &&
                        result.get(j)[0] <= result.get(i)[1]) {
                        result.get(i)[0] = Math.min(result.get(i)[0], result.get(j)[0]);
                        result.get(i)[1] = Math.max(result.get(i)[1], result.get(j)[1]);
                        result.remove(j);
                        merged = true;
                        break;
                    }
                }
                if (merged) break;
            }
        }
        return result.toArray(new int[0][]);
    }
}

Optimal: Sort + Linear Merge - O(n log n)

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

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

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

            if (intervals[i][0] <= last[1]) {
                last[1] = Math.max(last[1], intervals[i][1]);
            } else {
                merged.add(intervals[i]);
            }
        }

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

Java Architecture Insights

• Integer.compare(a, b) vs a - b: Always use Integer.compare(). Subtraction can overflow with extreme values (e.g., Integer.MIN_VALUE - 1).
• toArray(new int[0][]) vs toArray(new int[size][]): Modern JVMs optimize the zero-length version to be equally fast, and it’s cleaner.
• Why List<int[]> not LinkedList? ArrayList has better cache locality for sequential access. LinkedList only wins for frequent insertions/deletions in the middle.

---

3. Mental Model & Visualization

ASCII Diagram (intervals = [[1,3],[2,6],[8,10],[15,18]])

Input (sorted):
[1---3]
  [2------6]
              [8--10]
                       [15--18]

Merge Process:
[1---3] + [2------6] → [1------6]  (3 >= 2, overlap!)
[1------6] vs [8--10] → no overlap  (6 < 8)
[8--10] vs [15--18]   → no overlap  (10 < 15)

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

Senior Mental Trigger

“Overlapping ranges = sort by start, then greedily merge.”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 56	Merge Intervals	Medium
LC 57	Insert Interval	Medium
LC 252	Meeting Rooms	Easy
LC 253	Meeting Rooms II	Medium
LC 986	Interval List Intersections	Medium

FAANG ‘Aha!’ Level (Hard/Unintuitive)

#	Problem	Difficulty
LC 435	Non-overlapping Intervals	Medium
LC 759	Employee Free Time	Hard
LC 352	Data Stream as Disjoint Intervals	Hard
LC 1235	Maximum Profit in Job Scheduling	Hard
LC 452	Minimum Number of Arrows to Burst Balloons	Medium

---

5. Time & Space Complexity Table

Approach	Time	Space	Notes
Brute Force	O(n^2)	O(n)	Compare every pair repeatedly
Sort + Merge	O(n log n)	O(n)	Sorting dominates