Maximum Non-Overlapping Interval Scheduling
You have a list of $n$ tasks, each defined by a start time $s_i$ and an end time $e_i$. Two tasks overlap if their intervals intersect (i.e., one starts before the other ends).
**(a)** Design an $O(n \log n)$ algorithm to select the maximum number of non-overlapping tasks on a single machine. Prove that your algorithm is optimal.
**(b)** Now suppose you have $m$ identical machines. Each machine can run non-overlapping tasks, and you want to maximize the total number of tasks scheduled across all machines. Propose a greedy algorithm that runs in $O(n \log n)$ time using a min-heap, and explain why it works.
**Constraints:**
-
\le n \le 10^5$
-
\le m \le n$
- $0 \le s_i < e_i \le 10^9$
**Example 1 (single machine):**
```
Input: tasks = [(1,3), (2,5), (4,7), (6,9), (8,10)], m = 1
Output: 3
Explanation: Sort by end time -> (1,3),(2,5),(4,7),(6,9),(8,10).
Pick (1,3). Skip (2,5) (starts at 2 < 3). Pick (4,7). Skip (6,9)
(starts at 6 < 7). Pick (8,10). Total = 3.
```
**Example 2 (multi-machine):**
```
Input: tasks = [(1,4), (2,5), (5,7), (6,9)], m = 2
Output: 4
Explanation: Sort by start time -> (1,4),(2,5),(5,7),(6,9).
(1,4) -> Machine 1 (free). (2,5) -> Machine 2 (Machine 1 busy until 4).
(5,7) -> Machine 1 (free at 4, and 5 >= 4). (6,9) -> Machine 2
(free at 5, and 6 >= 5). All 4 tasks scheduled.
```
Open the full interactive solver, hints, and worked solution →