Finish Time of Tasks I - Video Solutions

Problem Overview: You are given tasks with a start time and a processing duration. Only one task can run at a time. If the processor is idle, it waits for the next task’s start time; otherwise the task starts when the previous one finishes. The goal is to compute the exact finish time for each task.

Approach 1: Time Simulation (Brute Force) (Time: O(T), Space: O(1))

The most literal way is to simulate time unit by unit. Maintain a pointer to the current task and increment a global clock. When the clock reaches a task’s start time, begin processing it and keep advancing the clock until its duration completes. Record the finish time, then move to the next task. This works but becomes inefficient if time values are large because the algorithm iterates across every intermediate timestamp. It demonstrates the mechanics clearly but is rarely acceptable in interviews.

Approach 2: Greedy Running Clock (Optimal) (Time: O(n), Space: O(1))

Instead of advancing time step by step, jump directly to meaningful events. Track a variable currentTime representing when the processor becomes free. For each task, compute its actual start time as max(currentTime, start[i]). The finish time is startActual + duration[i]. Update currentTime to this finish time and continue. This greedy simulation works because tasks are processed in order and the machine can only handle one job at a time, so the only state that matters is when the previous task finished.

This approach effectively compresses idle periods and processing intervals into a single calculation. Each task requires constant work: a comparison, addition, and assignment. The result is linear time with constant extra memory, making it suitable even when the number of tasks is large.

Conceptually this falls under greedy algorithms and simulation. The input handling typically uses simple array traversal, and no auxiliary data structures are required.

Recommended for interviews: The greedy running clock approach. Interviewers expect you to recognize that explicit time simulation is unnecessary. Showing the brute-force idea first demonstrates understanding of the system behavior, while the O(n) event-based simulation shows the optimization skill they are actually evaluating.