Minimum Time to Complete All Tasks

Minimum Time to Complete All Tasks

What is this problem about?

The Minimum Time to Complete All Tasks problem gives you a list of tasks, each with a start time, end time, and required duration. A computer can run each task during any interval within [start, end] as long as the total running time equals the required duration. The computer can only run one task at a time. Find the minimum total time the computer needs to be running. This hard Minimum Time to Complete All Tasks coding problem uses a greedy stack-based interval scheduling strategy.

Why is this asked in interviews?

Snap and Google ask this hard problem because it requires a non-trivial greedy insight: tasks with earlier deadlines should be scheduled last within their window (to maximize overlap with tasks that have later deadlines). The array, sorting, binary search, stack, and greedy interview pattern is fully represented, and the stack helps efficiently determine how much of the required duration is already covered by existing scheduling.

Algorithmic pattern used

Greedy sorting + stack/bitset. Sort tasks by their end time. For each task, use a boolean array (or stack) to track which time units are already scheduled. Count how many time units within [start, end] are already covered. If fewer than required, greedily fill the remaining needed time units from the right of the task's window (latest possible — to maximize overlap with future tasks). Update the running count.

Example explanation

Tasks: [(1,3,2), (2,5,3), (4,5,1)]. Sort by end time: same order.

• Task (1,3,2): window [1,3], need 2 units. No prior coverage. Schedule at times 2,3. Running count = 2.
• Task (2,5,3): window [2,5], need 3 units. Times 2,3 already covered = 2 units. Need 1 more. Schedule at time 5. Running count = 3.
• Task (4,5,1): window [4,5]. Time 5 already scheduled. Need 1 unit — already covered. No new time added. Total = 3 units.

Common mistakes candidates make

• Scheduling from the left of each window instead of the right (loses future overlap opportunities).
• Not sorting by end time first.
• Not tracking which specific time units are already scheduled (just counting isn't enough).
• Overcounting already-covered time within the window.

Interview preparation tip

Hard greedy scheduling problems often require thinking about "which direction to fill" — and the answer is almost always "from the latest possible time." This maximizes overlap with tasks that have tighter deadlines. Sorting by deadline (end time) and filling greedily from the right of each window is a powerful pattern. Practice interval scheduling problems with duration requirements — they appear in Google and Snap interviews and require the same deadline-first, right-fill greedy strategy.