Maximize Non-Overlapping Task Scheduling Efficiency
Company: Pinterest
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### 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.
Overview: This question evaluates understanding of interval scheduling and resource optimization, focusing on reasoning about time intervals and conflict-free selection of tasks.
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
Hints
- Sort intervals by their end time ascending.
- Greedily pick an interval if its start >= the end of the last chosen interval.
- Half-open boundary allows choosing an interval starting exactly at the previous end.