Greedy Scheduling And Resource Reuse

What's being tested

Candidates must show proficiency with greedy scheduling and resource reuse: converting temporal/resource constraints into an algorithmic strategy that minimizes concurrent resource count. Interviewers probe ordering (sorting/sweep), reuse tracking (min-heap or multiset), and correctness under ties and edge cases like simultaneous end/start. For dependency-flavored variants, they expect topological ordering and cycle detection to layer execution before applying parallelism limits.

Patterns & templates

• Sort + sweep-line by start time, maintain active resource end-times in a min-heap (heapq); reuse when smallest end ≤ new start, O(n log n).

• Min-heap of end times: push trip/service end, pop while top ≤ current start; heap size = concurrent resources needed.

• Greedy assignment: always reuse earliest-finishing resource; proven optimal for interval partitioning (activity/interval scheduling duals).

• Kahn's algorithm for DAGs: compute in-degree, extract zero-degree nodes per layer to form parallelizable batches, O(V+E).

• Detect cycles with DFS (coloring) or Kahn; if cycle exists, no valid layered startup ordering.

• Concurrency bounding: after layering, treat each layer as set of independent tasks and schedule with a thread pool / semaphore, O(total tasks log k).

• Edge-case tie rules: define whether end==start allows reuse; implement consistent comparator to avoid off-by-one bugs.

Common pitfalls

Pitfall: Sorting only by start time and ignoring equal-time end/start semantics loses reuse opportunities or double-counts resources.

Pitfall: Using an unsized array or naive nested loops yields O(n^2) for large n; prefer heap-based O(n log n).

Pitfall: For dependency problems, returning any topological order without checking cycles will miss unsatisfiable inputs.