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 (one starts strictly before the other ends); back-to-back tasks $[a,b]$ and $[b,c]$ do NOT overlap.
Implement the function:
``` schedule_counts(tasks, m) ```
tasksis a list of[start, end]pairs (withstart < end).mis the number of identical machines.
Return a 2-element list [single, multi]:
- (a)
single= the maximum number of non-overlapping tasks schedulable on ONE machine. Use the classic earliest-end greedy ($O(n\log n)$): sort by end time and repeatedly pick the next task whose start is $\ge$ the last chosen end. - (b)
multi= the maximum TOTAL number of tasks schedulable across $m$ identical machines. A set of tasks fits on $m$ machines iff no point in time is covered by more than $m$ of them, so this maximizes the number of tasks selected subject to overlap depth $\le m$. Note that when $m = 1$,multiequalssingle.
Constraints: - $1 \le n \le 10^5$ - $1 \le m \le n$ - $0 \le s_i < e_i \le 10^9$
Example
schedule_counts([[1,3],[2,5],[4,7],[6,9],[8,10]], 1) -> [3, 3]
On a single machine the earliest-end greedy picks $(1,3)$, $(4,7)$, $(8,10)$ for 3 tasks; with $m = 1$ the multi-machine count is the same, so both entries are 3.
Hints
- For part (a), think about which property of a task you should sort by. Earliest start? Shortest duration? Earliest finish? Try counterexamples for each.
- The exchange argument is the standard technique for proving greedy optimality: show that for every task in the optimal solution, the greedy task finishes at least as early.
- For part (b), you need to track when each machine becomes free. A min-heap keyed on machine end-times lets you find the earliest-free machine in $O(\log m)$.
Worked Solution
How to Think About It: This is the classic interval scheduling problem. For part (a) the key greedy insight is: always pick the task that finishes earliest, because finishing early leaves the most room for future tasks. For part (b) the crucial observation is that a set of intervals is schedulable on $m$ machines iff at no point in time are more than $m$ of them active (for interval graphs, min machines needed = maximum overlap depth). So "maximize total tasks on $m$ machines" means "select the largest subset whose overlap depth never exceeds $m$." In particular, when $m = 1$ this reduces exactly to part (a).
Algorithm (Part a) -- Earliest Deadline First: Sort tasks by end time; keep last_end = -inf; for each task, if its start $\ge$ last_end, select it and update last_end. This is optimal by the standard exchange argument (the greedy solution's $i$-th task finishes no later than any optimal solution's $i$-th task, so it never runs out of room first).
Algorithm (Part b) -- Multi-Machine, count-optimal: Process tasks in end-time order. Maintain each machine's current free-time. For each task, assign it to a machine that is free by the task's start; among the free machines pick the one that freed up latest (best fit), keeping earlier-freeing machines available for later tasks. If no machine is free in time, skip the task. Processing in end order means each newly assigned end is the largest so far, which keeps the greedy exchange-argument optimality and correctly reduces to part (a) at $m = 1$.
> Note: a common but WRONG approach is to sort by start time and assign to the earliest-free machine. That schedules a valid (feasible) assignment but does not maximize the number of tasks — it fails cases like $m=1$ where it can pick fewer than the single-machine optimum.
Code:
```python import bisect
def schedule_counts(tasks, m): # Part (a): single machine -- maximum number of non-overlapping tasks. # Classic earliest-deadline-first greedy (sort by end time). single = 0 last_end = float('-inf') for s, e in sorted(tasks, key=lambda x: x[1]): if s >= last_end: single += 1 last_end = e
# Part (b): m identical machines -- maximize the TOTAL number of tasks # scheduled. A set of tasks is schedulable on m machines iff no point in # time is covered by more than m of them. Greedily process tasks by end # time and assign each to a machine that is free by the task's start; among # free machines pick the one that freed up latest (best fit), so machines # that freed earlier stay available for later tasks. If no machine is free # in time, the task is skipped. frees = [float('-inf')] * m # kept sorted ascending multi = 0 for s, e in sorted(tasks, key=lambda x: x[1]): # rightmost machine whose free time is <= s i = bisect.bisect_right(frees, s) - 1 if i >= 0: frees.pop(i) bisect.insort(frees, e) multi += 1
return [single, multi] ```
Complexity: Both parts are $O(n \log n)$: sorting dominates, and each of the $n$ tasks in part (b) does an $O(\log m)$ search/insert into the machine free-time structure.
Intuition
Interval scheduling is the canonical example of greedy algorithms done right. The earliest-finish-time rule works because it is the most conservative choice -- by finishing as early as possible, you maximize the remaining time window for future tasks. Any other rule (shortest job, earliest start) can be tricked by adversarial inputs. The exchange argument is the standard proof technique for greedy algorithms: you show that swapping any optimal choice for the greedy choice never makes things worse.
The multi-machine extension is equally elegant. Instead of asking "does this task fit after the last one?" you ask "does this task fit on any machine?" -- and a min-heap answers that in logarithmic time. This pattern shows up constantly in systems design and scheduling: any time you have $m$ parallel resources and want to pack jobs efficiently, a priority queue on resource availability is the go-to data structure. In quantitative finance, similar scheduling logic appears in order execution (routing orders across venues with different latencies) and in parallel simulation architectures.