LeetCode Weekly Contest 467 | Problems 3683 & 3684 | Full Step-by-Step Solution + Intuition
Earliest Time to Finish One Task - Video Solution
Watch 10 video solutions for Earliest Time to Finish One Task, a easy level problem involving Array. This walkthrough by Navdeep R has 337 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a 2D integer array tasks where tasks[i] = [si, ti].
Each [si, ti] in tasks represents a task with start time si that takes ti units of time to finish.
Return the earliest time at which at least one task is finished.
Example 1:
Input: tasks = [[1,6],[2,3]]
Output: 5
Explanation:
The first task starts at time t = 1 and finishes at time 1 + 6 = 7. The second task finishes at time 2 + 3 = 5. You can finish one task at time 5.
Example 2:
Input: tasks = [[100,100],[100,100],[100,100]]
Output: 200
Explanation:
All three tasks finish at time 100 + 100 = 200.
Constraints:
1 <= tasks.length <= 100tasks[i] = [si, ti]1 <= si, ti <= 100
Approach Overview
Problem Overview: You receive two arrays representing tasks: a start time and the duration required to complete that task. The goal is to determine the earliest possible time at which any single task can finish. For each task, compute finish = start[i] + duration[i] and return the minimum finish time.
Approach 1: Sort by Finish Time (O(n log n) time, O(n) space)
A straightforward approach computes the finish time for every task and sorts them to find the smallest completion time. Create a list where each entry stores start[i] + duration[i]. After computing these values, sort the list and return the first element. Sorting guarantees the earliest completion appears at the front. This approach works but performs unnecessary work because you only need the minimum value. Sorting increases the time complexity to O(n log n) and requires O(n) extra space for the computed finish times.
Approach 2: Single Pass Minimum (O(n) time, O(1) space)
The optimal approach scans the arrays once while tracking the smallest completion time seen so far. For each index i, compute finish = start[i] + duration[i]. Compare it with the current minimum and update if it is smaller. After processing all tasks, the stored minimum represents the earliest possible completion time. This works because the problem reduces to finding the minimum value of a derived expression across an array. No additional data structures are required.
This pattern appears frequently in array scanning problems where the answer depends on a simple transformation of each element. Instead of storing intermediate results, compute the value and update a running minimum. The algorithm performs a constant amount of work per element, which keeps the time complexity at O(n) and space complexity at O(1). Similar techniques are used in problems involving minimum cost calculations or earliest event times.
Recommended for interviews: The single pass approach. Interviewers expect you to recognize that sorting is unnecessary when you only need the minimum value. Mentioning the sorting idea shows baseline reasoning, but implementing the linear scan demonstrates strong understanding of array traversal and optimal complexity analysis.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort by Finish Time | O(n log n) | O(n) | Conceptual baseline when transforming tasks into finish times and sorting them |
| Single Pass Minimum | O(n) | O(1) | Optimal solution when you only need the earliest finish time |