Two Snapshots of Every Rehearsal

A yearbook photographer visits the drama club. rehearsals[i] = [a, b] means rehearsal i is in progress at every whole minute a, a + 1, ..., b (both ends included). The photographer takes snapshots at whole minutes; one snapshot at minute t shows every rehearsal in progress at t. The editor wants every rehearsal to appear in snapshots taken at at least two different minutes. Return the smallest number of snapshot minutes needed.

Rehearsals may overlap, nest or repeat. An empty list needs 0 snapshots.

Examples

Input:  rehearsals = [[1, 3], [3, 7], [8, 9]]
Output: 5
Explanation: Minutes 2, 3, 7, 8, 9 work: [1, 3] gets 2 and 3, [3, 7] gets 3 and 7,
[8, 9] gets 8 and 9. Four minutes cannot do it.

Input:  rehearsals = [[1, 4], [2, 6], [3, 5]]
Output: 2
Explanation: Minutes 3 and 4 lie inside all three rehearsals.

Constraints

• 0 <= len(rehearsals) <= 6 * 10**4
• 0 <= a < b <= 10**9 (every rehearsal spans at least two whole minutes)
• Target complexity: O(n log n). Rechecking every earlier snapshot for each rehearsal is too slow for the largest tests.

Goals

• Extend the one-point stabbing greedy to intervals that need two points
• Choose a sort order whose tie-break makes the greedy choice safe
• Track only the two most recent points instead of every point placed