37. Activity Selection

Medium

Topics

Helpful tools to learn & understand

Visualize LogicActive Simulator

Watch key transitions, pointers, and variables update step-by-step.

Open

Check Solutions

Read clean, documented implementations across multiple patterns.

View Code

Thinkpad (Draw & Note)

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]

Output: 1

Explanation: [1,3] overlaps with [1,2], [2,3], [3,4]. Remove [1,3] to obtain non-overlapping intervals.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]

Output: 0

Explanation: You don't need to remove any of the intervals since they are already non-overlapping.

Example 4:

Input: intervals = [[1,100],[11,22],[1,11],[2,12]]

Output: 2

Explanation: Optimal solution involves removing [1,100] and either [1,11] or [2,12].

Example 5:

Input: intervals = []

Output: 0

Explanation: Empty input should return 0 as there are no intervals to remove.

Constraints:

•
•
•

Time Complexity

O(n log n)

Space Complexity

O(1)