algoadvance

Leetcode 2432. The Employee That Worked on the Longest Task

Problem Statement

A company assigns different tasks to its employees, where each task takes a certain amount of time to complete. The given tasks are tracked with their respective start times, and the system logs the task completion times in sequential order. Given a list of tasks, you need to determine which employee worked on the longest task. If there are multiple tasks with the same maximum duration, return the ID of the employee who completed the task first.

Clarifying Questions

1. What format is the input list in?
   • The input list is a list of lists/arrays where each sublist/array contains the start time, end time, and employee ID.
2. What should be returned?
   • Return the employee ID who worked on the longest task.
3. What if two or more tasks have the same duration?
   • Return the ID of the employee who completed the task first in case of a tie.
4. Are the tasks logged in chronological order?
   • Yes, the tasks are logged in chronological order in the input.

Strategy

1. Initialize Variables:
   • Use variables to track the maximum duration found (max_duration) and the employee ID associated with it (employee_id).
2. Iterate Over the List:
   • For each task, compute its duration.
   • Compare the task duration with the current max_duration:
     • If the duration is greater, update max_duration and employee_id.
     • If the duration is equal to max_duration, the first occurrence’s employee ID will be retained.
3. Return the Employee ID:
   • After processing all tasks, return the employee_id.

Code

public class Solution {
    public int hardestWorker(int n, int[][] logs) {
        int maxDuration = 0;
        int employeeId = -1;
        
        for (int i = 0; i < logs.length; i++) {
            int startTime = logs[i][0];
            int endTime = logs[i][1];
            int currentEmployeeId = logs[i][2];
            
            int duration = endTime - startTime;
            
            if (duration > maxDuration || (duration == maxDuration && currentEmployeeId < employeeId)) {
                maxDuration = duration;
                employeeId = currentEmployeeId;
            }
        }
        
        return employeeId;
    }
}

Time Complexity

• O(n): We iterate through the list of tasks only once, comparing the duration and updating the maximum duration and associated employee ID.

Space Complexity

• O(1): We only use a fixed amount of extra space for variables to track the maximum duration and employee ID.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?