Maximize Non-Overlapping Task Scheduling Efficiency

Scenario

Job scheduler on a single machine wants to maximise throughput.

Question

Given tasks with [start, end) times, return the maximum number of non-overlapping tasks that can be scheduled. Example: [[1,3],[1,5],[4,6]] ➝ 2.

Hints

Sort by end time and greedily pick compatible intervals.

Maximum Non-Overlapping Tasks Count

You are given a list of tasks, each represented as an interval [start, end) with integer times. Intervals are half-open: a task occupies time t where start <= t < end. Two tasks are compatible if they do not overlap, i.e., end_i <= start_j or end_j <= start_i. Return the maximum number of non-overlapping tasks that can be scheduled on a single machine. You may choose tasks in any order. If the list is empty, return 0.

Constraints

• 0 <= n <= 200000
• intervals[i] = [start_i, end_i]
• 0 <= start_i < end_i <= 10^9
• Half-open intervals: [start, end), no overlap if end_i <= start_j or end_j <= start_i
• Return an integer count

Examples

Example 1

Input: intervals = [[1,3],[1,5],[4,6]]
Output: 2

Explanation: Pick [1,3] and [4,6]. [1,5] overlaps with [1,3].

Example 2

Input: intervals = [[1,2],[2,3],[3,4],[0,6],[5,7]]
Output: 4

Explanation: Pick [1,2], [2,3], [3,4], and [5,7].

Hints

1. Sort intervals by their end time ascending.
2. Greedily pick an interval if its start >= the end of the last chosen interval.
3. Half-open boundary allows choosing an interval starting exactly at the previous end.

Approach

Sort intervals by their end time and iterate once, selecting an interval whenever its start time is not earlier than the end time of the last selected interval. This greedy strategy is optimal for maximizing the number of non-overlapping intervals.

• Time complexity: O(n log n)
• Space complexity: O(1) auxiliary (in-place sort)