Practice/Amazon/Leetcode 435. Non-overlapping Intervals

Leetcode 435. Non-overlapping Intervals

CodingMust

Problem

You are managing a conference venue that has received booking requests for various events. Each event is represented by a time interval with a start time and end time. Two events are considered non-overlapping if one ends exactly when the other starts (they can share an endpoint).

Your task is to determine the minimum number of event bookings you need to cancel so that all remaining events can be scheduled without any overlaps.

Requirements

1. Return the minimum number of events to cancel
2. Events that share only an endpoint are considered non-overlapping (can both be kept)
3. Each event is represented as [start, end] where start < end
4. If no cancellations are needed, return 0

Constraints

• 1 ≤ events.length ≤ 100,000
• events[i].length = 2
• -50,000 ≤ starti < endi ≤ 50,000
• Expected time complexity: O(n log n)
• Expected space complexity: O(1) or O(n) depending on language sorting behavior

Examples

Example 1:

Input: events = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: We can remove [1,3] and keep the other three events. The remaining events [1,2], [2,3], [3,4] share endpoints but don't overlap.

Example 2:

Input: events = [[1,2],[1,2],[1,2]] Output: 2 Explanation: All three events occupy the exact same time slot, so we must cancel 2 of them to avoid any overlap.

Example 3:

Input: events = [[1,2],[2,3]] Output: 0 Explanation: These events touch at time 2 but don't overlap, so no cancellations are needed.

Example 4:

Input: events = [[1,100],[11,22],[1,11],[2,12]] Output: 2 Explanation: One optimal solution keeps [1,11] and [11,22], requiring cancellation of [1,100] and [2,12].