Fit the most tasks into an hour across machine slots

Model the cluster as L = n * m independent lanes. A lane is one slot on
one machine. It runs tasks one after another, and everything it runs must end
by minute limit (60). A task cannot be split and cannot move between lanes.
So the question is: how many tasks can be packed into L bins of capacity 60?

Which tasks to pick. Some optimal answer always uses the k shortest
tasks. Take any feasible set of k tasks. If it contains a task longer than a
shorter task that was left out, swap them. The lane load only goes down, so the
set stays feasible. Repeat until the set is the k shortest. Two consequences:

• The answer is the largest k for which the k shortest tasks fit.
• Feasibility is monotone in k (drop the longest of a feasible set and it is
  still feasible), so we can binary search on k.

Brute force / first idea: greedy. Sort ascending and drop each task on the
least-loaded lane (min-heap) until the smallest load cannot take the next task.
This is O(T log T) and it is what most candidates write first. It is not
always optimal: with 2 lanes, limit 10 and tasks [3, 3, 4, 5, 5], greedy
builds {3, 4} and {3, 5} and then stops at 4, but {5, 5} and {3, 3, 4}
fit all 5. Naming this counterexample is a strong signal.

Exact method. Checking whether the k shortest tasks fit is bin packing,
which is NP-hard, so no polynomial algorithm is expected. For interview-sized
inputs we:

1. Drop tasks longer than the limit (they can never finish).
2. Bound k from above: the largest prefix whose total time is at most
   L * limit. Bound it from below with the greedy count (a greedy schedule is
   a real schedule).
3. Binary search k between the bounds. For each candidate, run a DFS that
   places tasks longest-first into lanes, with two prunings: skip a lane when
   it would overflow, and try only one lane among lanes with the same current
   load (they are interchangeable). This removes almost all symmetric work.

Invariants: lo is always a feasible count and hi is always an upper bound.
Every DFS state keeps every lane load at or below the limit.

from typing import List, Optional
import heapq


def greedy_count(n: int, m: int, durations: List[int], limit: int = 60) -> int:
    """Baseline: shortest task first onto the least-loaded slot. Not always optimal."""
    slots = [0] * (n * m)
    heapq.heapify(slots)
    done = 0
    for d in sorted(durations):
        if not slots or slots[0] + d > limit:
            break
        heapq.heapreplace(slots, slots[0] + d)
        done += 1
    return done


def pack(tasks: List[int], lanes: int, limit: int) -> Optional[List[List[int]]]:
    """Exact check: can every task go into `lanes` lanes of capacity `limit`?"""
    tasks = sorted(tasks, reverse=True)          # big items first: fail fast
    if not tasks:
        return [[] for _ in range(lanes)]
    if lanes == 0 or tasks[0] > limit or sum(tasks) > lanes * limit:
        return None
    loads = [0] * lanes
    bins: List[List[int]] = [[] for _ in range(lanes)]

    def place(i: int) -> bool:
        if i == len(tasks):
            return True
        d = tasks[i]
        tried = set()
        for j in range(lanes):
            # Lanes with equal load are interchangeable: try only one of them.
            if loads[j] in tried or loads[j] + d > limit:
                continue
            tried.add(loads[j])
            loads[j] += d
            bins[j].append(d)
            if place(i + 1):
                return True
            loads[j] -= d
            bins[j].pop()
        return False

    return bins if place(0) else None


def max_tasks(n: int, m: int, durations: List[int], limit: int = 60) -> int:
    """Most tasks n machines x m parallel slots can finish within `limit` minutes."""
    lanes = n * m
    tasks = sorted(d for d in durations if d <= limit)
    # Exchange argument: some optimal set is the k shortest tasks,
    # and if the k shortest fit then the k-1 shortest fit -> binary search on k.
    prefix, hi = 0, 0
    for d in tasks:                               # cheap upper bound by total time
        if prefix + d > lanes * limit:
            break
        prefix += d
        hi += 1
    lo = min(greedy_count(n, m, tasks, limit), hi)  # greedy result is feasible
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if pack(tasks[:mid], lanes, limit) is not None:
            lo = mid
        else:
            hi = mid - 1
    return lo

Let T be the number of tasks and L = n * m the number of lanes.

• greedy_count: O(T log T + T log L) time, O(L) space.
• Upper bound and sort: O(T log T).
• pack for k tasks: worst case exponential, about O(L^k), because exact
  bin packing is NP-hard. Longest-first order, the total-time check and the
  equal-load pruning make it fast for the sizes an interview uses
  (tens of tasks, a few dozen lanes). Space O(k + L) for the recursion and lanes.
• max_tasks: O(log T) calls to pack, and usually far fewer, because the
  greedy lower bound and the total-time upper bound are often equal or one
  apart.

• max_tasks(1, 1, [10, 20, 30, 40]) -> 3 (10 + 20 + 30 = 60 exactly).
• max_tasks(2, 1, [3, 3, 4, 5, 5], limit=10) -> 5; greedy_count on the
  same input -> 4 (the greedy counterexample).
• max_tasks(2, 2, [61, 70]) -> 0 (every task is longer than the limit).
• max_tasks(0, 3, [1, 2]) -> 0 (no machines).
• max_tasks(3, 2, []) -> 0 (no tasks).
• max_tasks(1, 2, [60, 60, 60]) -> 2 (one full-length task per lane).
• max_tasks(2, 2, [10, 5, 20, 15, 30, 25, 50, 45]) -> 8
  ({50, 10}, {45, 15}, {30, 25}, {20, 5}).
• max_tasks(1, 2, [35, 35, 30, 25, 25]) -> 4 ({35, 25}, {30, 25};
  all five need 150 > 120).
• max_tasks(1, 1, [30, 30, 1]) -> 2 (picking the 1 does not help a count
  of 3; total 61 > 60).

• Return the schedule, not just the count. pack already builds the lane
  contents. Map lane j back to machine j // m, slot j % m, and give each
  task its start time as the running sum in that lane.
• Tasks have priorities or values; maximize total value. The "k shortest"
  exchange argument breaks. With one lane it is 0/1 knapsack over capacity 60
  (O(T * 60) DP). With many lanes it is multiple knapsack; use DP over lanes
  for small inputs, or greedy by value density as a stated approximation.
• Tasks arrive online and must be placed immediately. No reordering is
  possible. Use best fit (the lane whose remaining time is the smallest that
  still fits) with a sorted structure of remaining capacities, and discuss its
  approximation behavior compared to the offline answer.
• Machines differ (different m per machine, or different speeds). Lanes
  get their own capacities (limit * speed); the DFS works unchanged with
  per-lane capacity, and the total-time upper bound uses the sum of capacities.
• Large inputs (thousands of tasks). Exact search is out. Say so, then use
  the greedy or first-fit-decreasing on the k shortest with a binary search,
  and report the gap to the total-time upper bound. If durations are small
  integers, a DP over lane-load multisets is possible for a few lanes.

Mid-level (L4)

• Asks what "m tasks simultaneously" means and models it as n * m lanes.
• Sorts ascending and fills lanes with a min-heap; handles tasks longer than
  60, zero machines and an empty list.
• Explains why shorter tasks are better for maximizing a count.

Senior (L5)

• Proves the "k shortest" exchange argument and the monotonicity in k.
• Finds or accepts that greedy can be suboptimal and gives a counterexample.
• Writes the binary search plus a correct backtracking check with pruning,
  and states the time cost honestly.

Staff (L6+)

• Names the problem as bin packing, says it is NP-hard, and frames the
  trade-off between exact search and approximations (FFD, bounds, gaps).
• Discusses how a real scheduler would do it: online placement, priorities,
  heterogeneous machines, preemption, and deadlines per task.
• Uses lower and upper bounds to avoid most expensive checks, and explains
  when the exact answer is worth its cost.