Maximum Non-Overlapping Interval Scheduling
Problem statement
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.
Show hint
Which single property of a task best predicts how much room it leaves for the tasks that come after it?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.