LeetCode Problem 3683

Difficulty: 🟢 Easy
Topics: Array

Solution

LeetCode 3683 - Earliest Time to Finish One Task

Problem Understanding

The problem gives us a list of tasks, where each task is represented by two integers:

• si, the time when the task starts.
• ti, the amount of time required to complete the task.

A task finishes at time:

$$\text{finishTime} = s_i + t_i$$

Our goal is to determine the earliest time at which at least one task has finished.

In other words, we need to compute the finishing time for every task and return the smallest finishing time among them.

For example, if we have:

tasks = [[1,6],[2,3]]

The first task finishes at:

1 + 6 = 7

The second task finishes at:

2 + 3 = 5

Since task two finishes first, the answer is 5.

The constraints are very small:

• There are at most 100 tasks.
• Start times and durations are at most 100.

These constraints tell us that even simple solutions will run extremely fast. We do not need any advanced data structures or optimization techniques.

Several edge cases are worth considering:

• A single task exists. In that case, its finishing time is automatically the answer.
• Multiple tasks may finish at exactly the same time.
• The earliest finishing task may not have the earliest start time.
• The earliest finishing task may not have the shortest duration.

The problem guarantees that at least one task exists, so we never need to handle an empty input.

Approaches

Brute Force Approach

A straightforward solution is to simulate the passage of time.

We could determine every possible time value and check whether any task finishes at that moment. Starting from time 0, we repeatedly test whether some task's finish time equals the current time. The first time that satisfies this condition is the answer.

This approach is correct because it examines times in increasing order and returns the first finishing event. However, it performs unnecessary work because the finish times are already directly computable from the input.

Although the constraints are small enough that this would still work, it is inefficient compared to simply computing finish times directly.

Optimal Approach

The key observation is that each task's finishing time is completely determined by:

$$s_i + t_i$$

Since we only care about the earliest task completion, we do not need to simulate time at all.

Instead, we compute the finishing time for every task and keep track of the minimum value encountered.

The smallest value among all si + ti calculations is exactly the earliest time when at least one task finishes.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × T)	O(1)	Check each time value until a task finishes
Optimal	O(n)	O(1)	Compute every finish time and keep the minimum

Here, n is the number of tasks and T is the range of times examined during simulation.

Algorithm Walkthrough

1. Initialize a variable to store the earliest finishing time.
2. Compute the finishing time of the first task using start + duration and use it as the initial answer.
3. Iterate through every task in the array.
4. For each task, calculate its finishing time as startTime + duration.
5. Compare this finishing time with the current minimum.
6. If the new finishing time is smaller, update the answer.
7. After processing all tasks, return the minimum finishing time found.

Why it works

Every task finishes exactly at time si + ti. The earliest task completion must therefore be the minimum value among all finishing times. The algorithm examines every task exactly once and maintains the smallest finish time seen so far. After the scan is complete, the stored minimum is guaranteed to be the earliest possible completion time.

Python Solution

from typing import List

class Solution:
    def earliestTime(self, tasks: List[List[int]]) -> int:
        earliest_finish = tasks[0][0] + tasks[0][1]

        for start_time, duration in tasks:
            finish_time = start_time + duration
            earliest_finish = min(earliest_finish, finish_time)

        return earliest_finish

The implementation begins by computing the finishing time of the first task and storing it as the current best answer.

Next, it iterates through all tasks. For each task, it computes the finish time using start_time + duration. The minimum between the current answer and the newly computed finish time is stored back into earliest_finish.

Once every task has been processed, the variable contains the smallest finishing time among all tasks, which is returned.

This directly follows the algorithm described above and uses only a few integer variables.

Go Solution

func earliestTime(tasks [][]int) int {
    earliestFinish := tasks[0][0] + tasks[0][1]

    for _, task := range tasks {
        finishTime := task[0] + task[1]
        if finishTime < earliestFinish {
            earliestFinish = finishTime
        }
    }

    return earliestFinish
}

The Go implementation follows the same logic as the Python version. It initializes the answer using the first task's finishing time and then iterates through the slice of tasks.

Since the maximum possible finish time is only 100 + 100 = 200, integer overflow is not a concern. The problem guarantees at least one task exists, so accessing tasks[0] is always safe.

Worked Examples

Example 1

Input

tasks = [[1,6],[2,3]]

Iteration Trace

Task	Start	Duration	Finish Time	Earliest Finish
Initial	1	6	7	7
[1,6]	1	6	7	7
[2,3]	2	3	5	5

Result

5

The second task finishes at time 5, which is earlier than time 7.

Example 2

Input

tasks = [[100,100],[100,100],[100,100]]

Iteration Trace

Task	Start	Duration	Finish Time	Earliest Finish
Initial	100	100	200	200
First	100	100	200	200
Second	100	100	200	200
Third	100	100	200	200

Result

200

All tasks finish at the same time, so the minimum finishing time is 200.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each task is processed exactly once
Space	O(1)	Only a few variables are used

The algorithm performs a single linear scan through the input array. No additional data structures proportional to the input size are allocated, so the space usage remains constant.

Test Cases

sol = Solution()

assert sol.earliestTime([[1, 6], [2, 3]]) == 5          # Example 1
assert sol.earliestTime([[100, 100], [100, 100], [100, 100]]) == 200  # Example 2

assert sol.earliestTime([[5, 10]]) == 15               # Single task
assert sol.earliestTime([[1, 1], [10, 10]]) == 2       # Earliest task is first
assert sol.earliestTime([[10, 10], [1, 1]]) == 2       # Earliest task is later in array

assert sol.earliestTime([[1, 10], [5, 1]]) == 6        # Later start, shorter duration
assert sol.earliestTime([[3, 7], [4, 6]]) == 10        # Equal finish times

assert sol.earliestTime([[100, 1], [1, 100]]) == 101   # Different starts, same finish
assert sol.earliestTime([[1, 100], [2, 2], [3, 3]]) == 4  # Minimum in middle

assert sol.earliestTime([[100, 100]]) == 200           # Maximum constraint values

Test Summary

Test	Why
[[1,6],[2,3]]	Verifies the first example
[[100,100],[100,100],[100,100]]	Verifies the second example
[[5,10]]	Single-task input
[[1,1],[10,10]]	Earliest completion appears first
[[10,10],[1,1]]	Earliest completion appears later
[[1,10],[5,1]]	Later start can still finish earlier
[[3,7],[4,6]]	Multiple tasks finish simultaneously
[[100,1],[1,100]]	Equal finish times from different inputs
[[1,100],[2,2],[3,3]]	Minimum occurs in the middle of the array
[[100,100]]	Maximum allowed values

Edge Cases

Single Task

When only one task exists, there is no comparison to perform. A common mistake is to assume multiple tasks are available and initialize incorrectly. The implementation handles this naturally because it initializes the answer using the first task and returns it after the loop.

Multiple Tasks Finishing at the Same Time

Different tasks may have different start times and durations but still produce the same finishing time. For example, [[1,4],[2,3]] gives finishing times of 5 and 5. The algorithm correctly returns 5 because it tracks the minimum value, regardless of how many times that value occurs.

Later Start Time Finishing Earlier

A task that starts later can still finish first if its duration is much shorter. For example, [[1,10],[5,1]] produces finishing times 11 and 6. An incorrect solution might focus only on the smallest start time or smallest duration. This implementation always computes the true finish time si + ti, ensuring the correct answer is found.

All Tasks Identical

If every task has the same start time and duration, every finishing time is identical. The algorithm still works because the minimum of identical values is that same value. No special handling is required.