algoadvance

Leetcode 2432. The Employee That Worked on the Longest Task

Problem Statement:

You are given a 0-indexed integer array logs, where logs[i] = [id_i, time_i] indicates that the i-th employee started the i-th task at time_i.

The task with logs[i] was completed at time_i + d_i, and no later tasks start earlier than this completion time.

Your goal is to find the id of the employee that worked on the task that had the longest duration. If there is a tie, return the smallest id.

Example:

Input: n = 3, logs = [[0,2],[1,3],[2,7]]
Output: 2

Clarifying Questions:

  1. What is the range of n and logs?
    • The number of employees n can be between 1 and 10^5.
    • The size of logs is equal to the number of tasks done and can be up to 10^5.
  2. Are the task times guaranteed to be sequenced correctly?
    • Yes, all tasks are carried out sequentially, and no later task starts earlier than the completion of a current task.
  3. Are time values guaranteed to be integers?
    • Yes, all given time values are integers.

Strategy:

  1. Initialize Variables: Initialize variables to keep track of maximum task duration and the employee ID associated with it.
  2. Iterate Through Logs: For each log entry, calculate the duration of the task by taking the difference between the current task start time and the previous task start time.
  3. Check Maximum Duration: Compare the calculated task duration with the current maximum duration and update if necessary.
  4. Edge Cases: Handle the scenario where there is only one log entry.

Code:

#include <vector>
#include <algorithm>
#include <climits>

int hardestWorker(int n, std::vector<std::vector<int>>& logs) {
    int maxDuration = INT_MIN;
    int employeeId = INT_MAX;
    
    int prevTime = 0;
    
    for (const auto& log : logs) {
        int id = log[0];
        int startTime = log[1];
        
        // Compute duration of the current task
        int taskDuration = startTime - prevTime;
        
        // Check if this duration is longer than the current max duration
        if (taskDuration > maxDuration || 
            (taskDuration == maxDuration && id < employeeId)) {
            maxDuration = taskDuration;
            employeeId = id;
        }
        
        // Update previous task complete time to current task start time
        prevTime = startTime;
    }
    
    return employeeId;
}

Time Complexity:

This solution ensures efficient handling of potentially large input sizes due to its linear time complexity.

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