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.Problem Overview: You receive a list of logs where logs[i] = [employeeId, leaveTime]. Tasks are executed sequentially, and each employee works on exactly one task at a time. The duration of a task is the difference between the current leaveTime and the previous task's finish time. Your goal is to find the employee who worked on the longest single task. If multiple employees have the same longest duration, return the smallest employee ID.
The logs are already sorted by completion time. That means you can process them in order and compute each task's duration using the difference between consecutive timestamps. The problem mainly tests careful array traversal and comparison logic using basic operations on a array.
Approach 1: Iterative Comparison Approach (O(n) time, O(1) space)
Traverse the log array once while tracking the previous task's finish time. For each log entry, compute the task duration using duration = leaveTime - previousLeave. Maintain two variables: the maximum duration seen so far and the employee ID associated with that duration. When a new duration exceeds the current maximum, update both values. If the duration ties with the maximum, choose the smaller employee ID. Since the logs are processed sequentially, a single pass is enough. This approach uses constant extra memory and relies purely on comparisons and arithmetic.
This technique is essentially a simple simulation of the execution timeline. Because each duration depends only on the previous timestamp, you don't need additional structures beyond a few variables. Many interview problems involving sequential events follow this exact pattern of "compute difference and track best".
Approach 2: Prefix Sum Optimization (O(n) time, O(n) space)
Another way to structure the logic is to explicitly store task durations using a prefix-difference idea. First iterate through the logs and compute an auxiliary array where duration[i] = logs[i][1] - logs[i-1][1] (with the first duration being logs[0][1]). Once durations are precomputed, perform a second pass to find the maximum duration and apply the same tie-breaking rule for employee IDs. This approach separates duration calculation from comparison logic, which can make debugging easier in some cases.
The method borrows the idea behind prefix sum transformations: convert cumulative timestamps into per-task durations so each entry becomes independent. However, the extra array means additional O(n) space, which is unnecessary for this problem.
Recommended for interviews: The iterative comparison approach is the expected solution. It runs in O(n) time with O(1) space and demonstrates that you understand how to derive task durations from sequential timestamps. Showing the brute reasoning (difference between consecutive times) first and then implementing the single-pass comparison proves strong fundamentals in array traversal and event timeline problems.
The idea is to iterate through the logs and calculate the time taken for each task. The task time is calculated as the difference between the leave time of the current task and the leave time of the previous task. We keep track of the maximum task time and the corresponding employee ID. If a task time is longer than the current maximum, or if it is equal but the ID is smaller, we update our records.
The function longestTaskEmployee iterates through the logs, and for each entry, calculates the duration of the task (handling the first entry separately since it starts at 0). It keeps track of the longest task time and the smallest ID involved in such tasks.
Time Complexity: O(m) where m is the number of logs.
Space Complexity: O(1) as we use only a constant amount of space.
Although not much optimization can be done beyond iterating to find the longest task, another approach involves using prefix sums or cumulative sums of timings to quickly query the execution time of any task. However, since the nature of the task list is linear, this provides similar performance in practice.
Despite the prefix sum concept, this C code effectively performs a single pass iteration, tracking cumulative time and updating task times to determine the longest task efficiently.
Time Complexity: O(m), still linear as it iterates once.
Space Complexity: O(1), maintains minimal state.
We use a variable last to record the end time of the last task, a variable mx to record the longest working time, and a variable ans to record the employee with the longest working time and the smallest id. Initially, all three variables are 0.
Next, we traverse the array logs. For each employee, we subtract the end time of the last task from the time the employee completes the task to get the working time t of this employee. If mx is less than t, or mx equals t and the id of this employee is less than ans, then we update mx and ans. Then we update last to be the end time of the last task plus t. Continue to traverse until the entire array is traversed.
Finally, return the answer ans.
The time complexity is O(n), where n is the length of the array logs. The space complexity is O(1).
Rust
| Approach | Complexity |
|---|---|
| Iterative Comparison Approach | Time Complexity: O(m) where m is the number of logs. |
| Prefix Sum Optimization | Time Complexity: O(m), still linear as it iterates once. |
| Direct Traversal | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Comparison Approach | O(n) | O(1) | Best general solution. Single pass over the logs with constant memory. |
| Prefix Sum Optimization | O(n) | O(n) | Useful when you want explicit duration storage or easier debugging of intermediate values. |
The Employee that worked on the longest task - Leetcode Weekly Contest 314 • Gopala Krishna Reddy Maguluri • 593 views views
Watch 9 more video solutions →Practice The Employee That Worked on the Longest Task with our built-in code editor and test cases.
Practice on FleetCode