LeetCode 2432. The Employee That Worked on the Longest Task Solution in Java, C++, Python & More | Explanation + Code

Description

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, and
• leaveTimei 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 <= 500
• 1 <= logs.length <= 500
• logs[i].length == 2
• 0 <= idi <= n - 1
• 1 <= leaveTimei <= 500
• idi != idi+1
• leaveTimei are sorted in a strictly increasing order.

Solutions

Solution 1: Direct Traversal

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).

PythonJavaC++GoTypeScriptRustC

class Solution: def hardestWorker(self, n: int, logs: List[List[int]]) -> int: last = mx = ans = 0 for uid, t in logs: t -= last if mx < t or (mx == t and ans > uid): ans, mx = uid, t last += t return ans(code-box)

class Solution { public int hardestWorker(int n, int[][] logs) { int ans = 0; int last = 0, mx = 0; for (int[] log : logs) { int uid = log[0], t = log[1]; t -= last; if (mx < t || (mx == t && ans > uid)) { ans = uid; mx = t; } last += t; } return ans; } }(code-box)

class Solution { public: int hardestWorker(int n, vector<vector<int>>& logs) { int ans = 0, mx = 0, last = 0; for (auto& log : logs) { int uid = log[0], t = log[1]; t -= last; if (mx < t || (mx == t && ans > uid)) { mx = t; ans = uid; } last += t; } return ans; } };(code-box)

func hardestWorker(n int, logs [][]int) (ans int) { var mx, last int for _, log := range logs { uid, t := log[0], log[1] t -= last if mx < t || (mx == t && uid < ans) { mx = t ans = uid } last += t } return }(code-box)

function hardestWorker(n: number, logs: number[][]): number { let [ans, mx, last] = [0, 0, 0]; for (let [uid, t] of logs) { t -= last; if (mx < t || (mx == t && ans > uid)) { ans = uid; mx = t; } last += t; } return ans; }(code-box)

impl Solution { pub fn hardest_worker(n: i32, logs: Vec<Vec<i32>>) -> i32 { let mut res = 0; let mut max = 0; let mut pre = 0; for log in logs.iter() { let t = log[1] - pre; if t > max || (t == max && res > log[0]) { res = log[0]; max = t; } pre = log[1]; } res } }(code-box)

#define min(a, b) (((a) < (b)) ? (a) : (b)) int hardestWorker(int n, int** logs, int logsSize, int* logsColSize) { int res = 0; int max = 0; int pre = 0; for (int i = 0; i < logsSize; i++) { int t = logs[i][1] - pre; if (t > max || (t == max && res > logs[i][0])) { res = logs[i][0]; max = t; } pre = logs[i][1]; } return res; }(code-box)

Solution 2

Rust

impl Solution { pub fn hardest_worker(n: i32, logs: Vec<Vec<i32>>) -> i32 { let mut ans = 0; let mut mx = 0; let mut last = 0; for log in logs { let uid = log[0]; let t = log[1]; let diff = t - last; last = t; if diff > mx || (diff == mx && uid < ans) { ans = uid; mx = diff; } } ans } }(code-box)