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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m), still linear as it iterates once.
Space Complexity: O(1), maintains minimal state.
| 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. |
Leetcode 128 - LONGEST CONSECUTIVE SEQUENCE • NeetCode • 455,447 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