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.
Quick Answer: 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
Solution
def max_non_overlapping_tasks(intervals: list[list[int]]) -> int:
# Greedy by earliest finishing time
if not intervals:
return 0
intervals.sort(key=lambda x: (x[1], x[0]))
count = 0
current_end = float('-inf')
for s, e in intervals:
if s >= current_end:
count += 1
current_end = e
return count
Explanation
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).
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.