2432. The Employee That Worked on the Longest Task
Problem Description
In this problem, we are working with a record of tasks completed by different employees, each of whom has a unique identifier ranging from 0 to n - 1
. There is a given 2D integer array named logs
, where each element is a pair consisting of an employee id and a leave time. This array essentially tracks which employee finished which task and the time they finished it. The leave times are unique for each task.
Each task begins immediately after the previous one ends, and the first task (0th task) starts at time 0. The goal is to determine the employee id that worked on the task that took the longest time to complete. In case there are tasks that took the same maximum amount of time and were worked on by different employees, the employee with the smaller id is the one that should be returned.
Intuition
To solve this problem, we need to determine the duration that each employee spent on their task. Since the tasks are completed in a serial manner, the duration an employee spent on a task can be calculated by subtracting the finish time of the previous task from the finish time of the current task. The 0th
task starts at time 0, so for this first task, the duration is simply the finishing time of the task since it started at time 0.
Now, we keep track of the maximum duration observed and the associated employee id. As we iterate through the logs
array, we compare the current task's duration with what we've recorded as the maximum duration so far. If the current duration is greater, we update our records to now consider this as the max duration, and we update the "hardest worker" to be the current employee's id. If the current duration matches the maximum duration seen so far (a tie), we check the employee ids involved and update our "hardest worker" to be the employee with the smaller id.
The managing of the "last" task finish time is critical because it marks the start of the next task (other than the first task, which starts at time 0). After determining the duration for the current task, we update the "last" finish time to match the current task's finish time, effectively setting it up for the next comparison.
The given solution employs a for-loop to scan the logs
list once, maintaining the current maximum duration and the employee with the smallest id that worked for this duration. Once the loop is complete, it returns the identifier of the "hardest worker" as the result.
Solution Approach
The solution approach uses a simple linear scan algorithm to determine which employee worked the longest on a single task. It makes use of basic comparison and arithmetic operations to track and update the task with the longest duration and the corresponding employee id.
Here is the step-by-step explanation of the solution algorithm:
-
Initialize three variables:
last
,mx
, andans
. Set bothlast
andmx
(maximum task duration so far) to0
, andans
(the id of the employee who worked the longest) to the first employee's id. -
Iterate over each entry in the
logs
list. Each entry is a pair[uid, t]
which stands for an employee id (uid
) and the time the task was completed (t
). -
For each entry, update the duration of the current task by calculating the difference between the current task's completion time
t
and the last task's completion time (stored inlast
). The expression for this is:t -= last
-
Now check if the current duration
t
is greater than the maximum durationmx
or if there is a tie and the current employee's id is smaller than the one previously stored. If either condition is true:- Update
mx
to match the current durationt
. - Update
ans
to the current employee's id (uid
).
- Update
-
Update the
last
task completion time to account for the subsequent task's duration calculation:last += t
-
After processing all entries, return
ans
as the solution. This is the id of the employee who worked the most extended task.
The solution uses no additional data structures; it relies only on a few variables to track the information needed and operates with an O(n) time complexity where n is the number of entries in the logs
list. The algorithm is efficient as it scans the logs only once, and the space complexity is constant O(1), as no extra space is needed regardless of the size of the input list logs
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach:
Suppose we have these logs
for employees with durations in which they completed the tasks:
logs = [[0,3],[2,5],[0,10],[1,15]]
In this logs
array, the first element [0,3]
indicates that employee 0
finished a task at time 3
. The second element [2,5]
indicates that employee 2
finished the following task at time 5
; and so on.
Now, let's apply the solution approach:
-
We initialize
last
,mx
, andans
to0
since no task has been completed yet, and we need a starting point. -
We begin iteration with the first entry
[0,3]
. This task took3
time units because it started at time0
. We setmx
to3
andans
to0
, since this is the longest duration we have seen so far, and it belongs to employee0
.
last = 0 mx = 3 ans = 0
- We continue to the next entry
[2,5]
. The duration for this task is5 - last
which is2
(5 - 3
). This duration is not longer thanmx
which is3
, so we don't changemx
orans
. We then updatelast
to5
.
last = 5 mx = 3 ans = 0
- The next entry is
[0,10]
. The duration for this task is10 - last
which is5
(10 - 5
). This duration is greater than the currentmx
which is3
, so we updatemx
to5
andans
to0
. Then we update thelast
to10
.
last = 10 mx = 5 ans = 0
- The last entry is
[1,15]
. The duration for this task is15 - last
which is5
. This is equal to our currentmx
. Now, we compare the employee ids; since1
is larger than the currentans
which is0
, we keepans
as0
. We updatelast
to15
.
last = 15 mx = 5 ans = 0
- We have exhausted all entries, so we finish the iteration, and the
ans
is the final result. Employee0
is the one who worked the longest on a single task.
In this example, the final output would be 0
, which indicates that employee 0
worked the longest time on a task, which took 5
time units to complete.
Solution Implementation
1class Solution:
2 def hardestWorker(self, n: int, logs: List[List[int]]) -> int:
3 # Initialize variables:
4 # 'last_event_time' to capture the end time of the last event.
5 # 'max_duration' to store the duration of the longest task.
6 # 'hardest_worker_id' to store the ID of the hardest worker.
7 last_event_time = 0
8 max_duration = 0
9 hardest_worker_id = 0
10
11 # Iterate through the logs
12 for user_id, current_time in logs:
13 # Calculate the duration of the current task
14 current_duration = current_time - last_event_time
15
16 # Check if the current task duration is greater than the max duration found so far,
17 # or if it's equal and the current user ID is lower than the one stored.
18 if max_duration < current_duration or (max_duration == current_duration and hardest_worker_id > user_id):
19 # Update the hardest worker ID and the max task duration
20 hardest_worker_id, max_duration = user_id, current_duration
21
22 # Update 'last_event_time' for the next iteration
23 last_event_time = current_time
24
25 # Return the ID of the hardest worker
26 return hardest_worker_id
27
1class Solution {
2 public int hardestWorker(int n, int[][] logs) {
3 int employeeIdWithMaxWork = 0; // To hold the ID of the employee who worked the most in a single log
4 int lastEndTime = 0; // To keep track of the end time of the last task
5 int maxDuration = 0; // To hold the maximum duration of work done continuously
6
7 // Iterate through the work logs
8 for (int[] log : logs) {
9 int currentEmployeeId = log[0]; // ID of the current employee
10 int currentTime = log[1]; // Time when the current task was finished
11
12 // Calculate the duration the current employee worked
13 int currentDuration = currentTime - lastEndTime;
14
15 // Determine if the current employee worked more than the previous max,
16 // or if it's equal to the max duration and the current employee's ID is smaller.
17 if (maxDuration < currentDuration || (maxDuration == currentDuration && employeeIdWithMaxWork > currentEmployeeId)) {
18 employeeIdWithMaxWork = currentEmployeeId; // Update the employee ID with the max work
19 maxDuration = currentDuration; // Update the max duration
20 }
21
22 // Update the end time of the last task to the current task's end time
23 lastEndTime = currentTime;
24 }
25 return employeeIdWithMaxWork; // Return the ID of the employee who worked the hardest
26 }
27}
28
1#include <vector>
2
3class Solution {
4public:
5 // Function to find the hardest worker where 'n' is the number of workers,
6 // and 'logs' is the vector of vectors containing the worker ID and the time they logged out.
7 int hardestWorker(int n, vector<vector<int>>& logs) {
8 int hardestWorkerId = 0; // Store the ID of the hardest worker.
9 int maxWorkDuration = 0; // Store the maximum work duration.
10 int lastLogTime = 0; // Store the last log time to calculate the duration.
11
12 // Loop through the logs to identify the hardest worker.
13 for (auto& log : logs) {
14 int workerId = log[0]; // Get the worker's ID from the log.
15 int logTime = log[1]; // Get the log time from the log.
16
17 // Calculate the work duration for the current worker.
18 int workDuration = logTime - lastLogTime;
19
20 // Check if this worker has worked more or equal than the current maximum work duration
21 // and if this worker has a smaller ID than the current hardest worker's ID in case of a tie.
22 if (maxWorkDuration < workDuration || (maxWorkDuration == workDuration && hardestWorkerId > workerId)) {
23 maxWorkDuration = workDuration; // Update the maximum work duration.
24 hardestWorkerId = workerId; // Update the hardest worker ID.
25 }
26
27 // Update the last log time for the next iteration.
28 lastLogTime = logTime;
29 }
30
31 // Return the ID of the hardest worker after all logs have been processed.
32 return hardestWorkerId;
33 }
34};
35
1// Define the function hardestWorker which takes a total number of workers (n)
2// and an array of logs with worker IDs and timestamps, and
3// returns the ID of the worker who worked the hardest.
4function hardestWorker(totalWorkers: number, logs: number[][]): number {
5 // Initialize variables:
6 // 'longestWork' to track the longest amount of work done.
7 // 'maxWorkDuration' to keep the maximum continuous work duration.
8 // 'lastTimestamp' to keep the last timestamp we calculated work duration from.
9 let [longestWorkId, maxWorkDuration, lastTimestamp] = [0, 0, 0];
10
11 // Iterate through each log entry.
12 for (let [workerId, timestamp] of logs) {
13 // Calculate the work duration by subtracting lastTimestamp from current timestamp.
14 let workDuration = timestamp - lastTimestamp;
15
16 // Check if the current work duration exceeds our maxWorkDuration or if it is equal and the workerId is lower.
17 if (maxWorkDuration < workDuration || (maxWorkDuration === workDuration && longestWorkId > workerId)) {
18 // Update the longestWorkId and maxWorkDuration with the current worker's ID and work duration.
19 longestWorkId = workerId;
20 maxWorkDuration = workDuration;
21 }
22
23 // Update lastTimestamp to calculate next work duration correctly.
24 lastTimestamp = timestamp;
25 }
26
27 // Return the ID of the worker who worked the hardest.
28 return longestWorkId;
29}
30
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n)
, where n
is the number of entries in the logs
list. The reason is that the code iterates through each log entry exactly once, performing a constant amount of work for each entry (updating variables and simple comparisons).
Space Complexity
The space complexity of the code is O(1)
because the code uses a fixed amount of space that does not depend on the input size. Variables last
, mx
, ans
, and any other temporary variables used during iteration do not scale with the size of the input, as they are simply storage for current and maximum time differences as well as the corresponding worker ID.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a good use case for backtracking?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!