The O(n) Club: Maximum Length of Pair Chain: The Greedy Way to Outsmart Your Calendar (and Interviewer)

The O(n) Club: Maximum Length of Pair Chain—The Greedy Way to Outsmart Your Calendar (and Interviewer)

⚡ TL;DR

This problem is like scheduling as many awkward coffee meetings as possible without time collisions. Naive you: check every possible chaining (slow, tiring, regrets all around). Smart you: sort pairs by end times, then greedily take any pair whose start comes after the previous end. Java gives you a two-espresso solution:

// Java
Arrays.sort(pairs, Comparator.comparingInt(a -> a[1]));
int count = 0, prev = Integer.MIN_VALUE;
for (int[] p : pairs) {
    if (p[0] > prev) {
        count++;
        prev = p[1];
    }
}
return count;

🧠 How Devs Usually Mess This Up

Classic mistakes include sorting pairs by their start value (nope), thinking you have to keep the original order (nope again), or assuming you must use every pair (not even close). This isn’t activity selection anxiety—just squeeze in as many as possible, with zero overlap, and you win.

🔍 What’s Actually Going On

Imagine each pair is an event in your calendar. You want to attend max events without running between overlapping rooms. If you always pick the next event that ends earliest, you leave your schedule wide open to stack more events later. That’s the greedy secret. Dynamic programming works too, but why pay extra when you already have a VIP pass for greedy?

🛠️ PseudoCode

• Sort by end value.
  

  Arrays.sort(pairs, Comparator.comparingInt(a -> a[1]));

• Initialize counter & marker.
  

  int count = 0; int prev = Integer.MIN_VALUE;

  Your “previous end” starts at -infinity, because time is a flat circle—or something.
• Loop over sorted pairs.
  

  for (int[] p : pairs) {
      if (p[0] > prev) {
          count++;
          prev = p[1];
      }
  }

  If the meeting starts after the last ended: you’re in!
• Return the count.

  return count;

💻 The Code

// Java
public int findLongestChain(int[][] pairs) {
    Arrays.sort(pairs, Comparator.comparingInt(a -> a[1]));
    int count = 0, prev = Integer.MIN_VALUE;
    for (int[] p : pairs) {
        if (p[0] > prev) {
            count++;
            prev = p[1];
        }
    }
    return count;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Sorting by start value: Don’t. Way sub-optimal chains and interview shame await.
• Assuming sequence must stay as given: Nope. Shuffle and pick, as long as each end < next start.
• All negative pairs or huge gaps? Logic is agnostic. Makes no difference—just order matters.
• Time/space: Sorting O(n log n) + O(n) scan, O(1) space (if we ignore input). Fast as heck for a chain problem.

🧠 Interviewer Brain-Tattoo

“Always pick the event that ends first—because life is too short for overlapping meetings and quadratic time.”