The O(n) Club: Merge Intervals — Where Meetings Go to Collide

The O(n) Club: Merge Intervals — Where Meetings Go to Collide

⚡ TL;DR

Have a bunch of intervals? Merge the overlaps, don’t ruin your calendar. Brute force: check every pair and unleash chaos. Smart way: sort by start, then sweep and merge. Java cheatcode below:

// intervals is List<int[]>
intervals.sort(Comparator.comparingInt(i -> i[0]));
List<int[]> res = new ArrayList<>();
for (int[] curr : intervals) {
    if (res.isEmpty() || res.get(res.size()-1)[1] < curr[0]) {
        res.add(curr);
    } else {
        res.get(res.size()-1)[1] = Math.max(res.get(res.size()-1)[1], curr[1]);
    }
}

🧠 How Devs Usually Mess This Up

Ah yes, the top three classics:

• No sort equals chaos. If you start merging unsorted intervals, expect to miss half the overlaps—like drinking decaf and wondering why you’re still tired.
• “Strictly less than” trap. Everyone goofs up and thinks [1,4] and [4,5] don’t overlap. They do. “Touching” is enough – merge ‘em and move.
• In-place contortions. Heroic attempts at updating arrays in-place usually end in spilled coffee. Much easier: use a nice output list.

🔍 What’s Actually Going On

Picture this: your calendar is a pile of sticky notes with all your meetings—randomly ordered, partly overlapping, definitely excessive. Sorted, they fall in line. Now just walk through, merging when one note grazes the next. Like a highlighter sliding across two adjacent tasks—if the intervals touch (end >= start), you fuse them, otherwise, just drop the next sticky on the pile. It’s less a sweep line algorithm, more a “don’t-let-your-meetings-stack-up” life lesson.

🛠️ PseudoCode

• Sort by interval start time.
  Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
• Make an output list for merged intervals.
• Loop over intervals:
  For each interval, check if it overlaps with the last in your output.
• If it doesn’t overlap:
  Add it. Time to grow the pile.
• If it does overlap:
  Stick them together by setting last.end = max(last.end, current.end).
• Celebrate:
  Enjoy your now-tidy output. And maybe a real coffee.

💻 The Code

import java.util.*;
 public class MergeIntervals {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return new int[0][2];
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> merged = new ArrayList<>();
        for (int[] interval : intervals) {
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge-palooza: No intervals? No problem. One interval? Even easier. Intervals like [3,4] and [4,5]? YES, merge them.
• Complexity Reality Check: Sorting O(n log n) takes the crown. Merging is O(n). Space? Just as big as your output (O(n) worst case).
• DIY Minimum: If you try “clever” tricks with fixed arrays and no auxiliary space… 🍀 Good luck, but it’s not worth the debugging hangover.

🧠 Interviewer Brain-Tattoo

“Merge what touches you (literally). If you forget to sort, you’re merging chaos, not intervals.”