There are n employees, each with a unique id from 0 to n - 1.
You are given a 2D integer array logs where logs[i] = [idi, leaveTimei] where:
idi is the id of the employee that worked on the ith task, andleaveTimei is the time at which the employee finished the ith task. All the values leaveTimei are unique.Note that the ith task starts the moment right after the (i - 1)th task ends, and the 0th task starts at time 0.
Return the id of the employee that worked the task with the longest time. If there is a tie between two or more employees, return the smallest id among them.
Example 1:
Input: n = 10, logs = [[0,3],[2,5],[0,9],[1,15]] Output: 1 Explanation: Task 0 started at 0 and ended at 3 with 3 units of times. Task 1 started at 3 and ended at 5 with 2 units of times. Task 2 started at 5 and ended at 9 with 4 units of times. Task 3 started at 9 and ended at 15 with 6 units of times. The task with the longest time is task 3 and the employee with id 1 is the one that worked on it, so we return 1.
Example 2:
Input: n = 26, logs = [[1,1],[3,7],[2,12],[7,17]] Output: 3 Explanation: Task 0 started at 0 and ended at 1 with 1 unit of times. Task 1 started at 1 and ended at 7 with 6 units of times. Task 2 started at 7 and ended at 12 with 5 units of times. Task 3 started at 12 and ended at 17 with 5 units of times. The tasks with the longest time is task 1. The employee that worked on it is 3, so we return 3.
Example 3:
Input: n = 2, logs = [[0,10],[1,20]] Output: 0 Explanation: Task 0 started at 0 and ended at 10 with 10 units of times. Task 1 started at 10 and ended at 20 with 10 units of times. The tasks with the longest time are tasks 0 and 1. The employees that worked on them are 0 and 1, so we return the smallest id 0.
Constraints:
2 <= n <= 5001 <= logs.length <= 500logs[i].length == 20 <= idi <= n - 11 <= leaveTimei <= 500idi != idi+1leaveTimei are sorted in a strictly increasing order.In #2432 The Employee That Worked on the Longest Task, you are given a list of logs where each entry contains an employee ID and the time they finished a task. The tasks are executed sequentially, meaning the next task starts exactly when the previous one ends. The duration of each task can therefore be computed using the difference between the current leaveTime and the previous task’s finish time.
A straightforward strategy is to iterate through the logs once while tracking the previous end time. For each log entry, calculate the task duration using duration = currentLeaveTime - previousLeaveTime. Maintain variables to store the longest duration seen so far and the corresponding employee ID. If two employees have the same task duration, the problem requires selecting the employee with the smaller ID.
This approach works efficiently because the logs are already sorted by time. A single pass through the array is sufficient to compute all durations and determine the answer.
The algorithm runs in O(n) time with O(1) extra space since only a few variables are required for tracking.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single pass over logs with duration tracking | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Find the time of the longest task
Store each employee’s longest task time in a hash table
For employees that have the same longest task time, we only need the employee with the smallest ID
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Each task begins exactly when the previous one ends, so the duration of a task is the difference between the current log's leave time and the previous task's leave time. For the first task, the previous time is considered to be 0.
Problems like this are common in technical interviews because they test array traversal, careful condition handling, and edge cases such as tie-breaking. While the exact question may vary, similar logic-based array problems often appear in FAANG-style interviews.
An array traversal is sufficient for this problem because the logs are already sorted by time. You only need a few variables to store the previous finish time, current maximum duration, and the best employee ID.
The optimal approach is to scan the logs array once and compute each task's duration by subtracting the previous finish time from the current leave time. While iterating, keep track of the maximum duration and the corresponding employee ID. If two durations are equal, choose the smaller employee ID.