Maximum Non-Overlapping Interval Scheduling

Reported in interviews at Citi Pinterest Groww

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)
  • tasks is a list of [start, end] pairs (with start < end).
  • m is 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$, multi equals single.

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.

Related free problems