The O(n) Club: Non-overlapping Intervals — Uninvite Guests, Save the Buffet

The O(n) Club: Non-overlapping Intervals — Uninvite Guests, Save the Buffet

⚡ TL;DR

Got a stack of intervals and need to make sure none of them overlap? Don’t panic and reach for backtracking—just go greedy: keep whoever leaves earliest. Sort by end time, walk right, boot everyone who can’t wait their turn. Java’s got your back:

// Sorry, late arrivals.
int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
    int end = Integer.MIN_VALUE, count = 0;
    for (int[] i : intervals) {
        if (i[0] < end) count++;
        else end = i[1];
    }
    return count;
}

🧠 How Devs Usually Mess This Up

If you instinctively sort by start time, you’ll wind up babysitting way too many overlaps. That’s like booking every band that arrives early for Coachella—they all overstay and the lineup is chaos. Ignore the start time. And don’t mix this up with “find the max keepers”—this is about minimizing what you toss, not maximizing keeps. Also, off-by-one errors on the end pointer are the interview zinger here—double check who you’re comparing, before blaming Java (again).

🔍 What’s Actually Going On

This is a dinner party with one chair. Each interval is a hungry guest. Whenever two overlap, you send the slower eater packing and keep the one who’ll vacate soonest. By always favoring the fastest finisher, you leave the most room for the next guest. Sort intervals by when they leave (end time), and one by one let them sit if the last seat’s free. If not, out they go. The secret sauce: earliest finishers = most survivors.

🛠️ PseudoCode

• Sort intervals by end time.
  Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]))
• Initialize end tracker to minus infinity (end = Integer.MIN_VALUE)—nobody’s come through yet.
• For each interval:
  • If interval[0] < end, overlap! Kick it out (count++).
  • Else, update end to this guest’s departure (end = interval[1]).
• Return count—your official uninvite tally.