Schedule Maximum Rakhi Celebrations

Problem Statement

It's Raksha Bandhan! A family has n sibling pairs, and each pair wants to do their rakhi ceremony together. However, there's only one pooja room available.

Each sibling pair i has a time window [start_i, end_i] during which they're both available for the ceremony. A ceremony takes the entire window.

Two ceremonies cannot overlap — the room can only host one at a time.

Find the maximum number of rakhi ceremonies that can be scheduled in the room.

Constraints

• 1 <= n <= 10^5
• 0 <= start_i < end_i <= 10^9
• A ceremony ending at time t allows another to start at time t (non-overlapping = no strict overlap)

Example

Input:

intervals = [[1, 3], [2, 5], [3, 7], [4, 6], [6, 8], [8, 10]]

Output: 4

Explanation: Select ceremonies [1,3], [4,6], [6,8], [8,10]. Maximum non-overlapping set.

What the Interviewer Expects

1. Greedy insight — always pick the interval that ends earliest. This leaves the most room for future intervals.
2. Sort by end time — this is the key step. Without it, greedy doesn't work.
3. Single pass after sort — track last end time, accept intervals whose start >= last end.
4. Time: O(n log n) for sort, O(n) for selection.
5. Proof of optimality — "earliest deadline first" is provably optimal for activity selection. Be ready to explain why.

Follow-ups

1. What if each ceremony has a "value" (some siblings are closer) and you want maximum total value? (Weighted interval scheduling — DP)
2. What if there are K rooms available instead of 1? What's the minimum K needed to fit all ceremonies?
3. What if intervals can be shortened (you can leave early)? Does the greedy approach change?
4. What if ceremonies have mandatory prep time — you need a 15-minute gap between any two? How do you adapt?
5. How does this relate to the "Meeting Rooms" problem on LeetCode?