2432. The Employee That Worked on the Longest Task

EasyArray
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Depth first search is equivalent to which of the tree traversal order?

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:

  1. Initialize three variables: last, mx, and ans. Set both last and mx (maximum task duration so far) to 0, and ans (the id of the employee who worked the longest) to the first employee's id.

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

  3. 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 in last). The expression for this is:

    1t -= last

  4. Now check if the current duration t is greater than the maximum duration mx 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 duration t.
    • Update ans to the current employee's id (uid).

  5. Update the last task completion time to account for the subsequent task's duration calculation:

    1last += t

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example 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:

1logs = [[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:

  1. We initialize last, mx, and ans to 0 since no task has been completed yet, and we need a starting point.

  2. We begin iteration with the first entry [0,3]. This task took 3 time units because it started at time 0. We set mx to 3 and ans to 0, since this is the longest duration we have seen so far, and it belongs to employee 0.

1last = 0
2mx = 3
3ans = 0
  1. We continue to the next entry [2,5]. The duration for this task is 5 - last which is 2 (5 - 3). This duration is not longer than mx which is 3, so we don't change mx or ans. We then update last to 5.
1last = 5
2mx = 3
3ans = 0
  1. The next entry is [0,10]. The duration for this task is 10 - last which is 5 (10 - 5). This duration is greater than the current mx which is 3, so we update mx to 5 and ans to 0. Then we update the last to 10.
1last = 10
2mx = 5
3ans = 0
  1. The last entry is [1,15]. The duration for this task is 15 - last which is 5. This is equal to our current mx. Now, we compare the employee ids; since 1 is larger than the current ans which is 0, we keep ans as 0. We update last to 15.
1last = 15
2mx = 5
3ans = 0
  1. We have exhausted all entries, so we finish the iteration, and the ans is the final result. Employee 0 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
Not Sure What to Study? Take the 2-min Quiz：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫