algoadvance

You are given n tasks that are assigned to n employees. Each task is represented by a tuple (employee_id, timestamp), where employee_id is the employee’s ID that completes the task, and timestamp is the time the task is completed. The list of tasks is provided in non-decreasing order of timestamps.

Your goal is to find out which employee has worked the longest on a single task. If there is a tie, return the employee with the smallest ID.

Write a function:

def hardestWorker(n: int, logs: List[List[int]]) -> int:

Return the employee_id of the employee who worked the longest on a single task.

Clarifying Questions

  1. Are task completion times in chronological order in the logs list?
    • Yes, the timestamps are given in non-decreasing order.
  2. What should be returned in case of a tie in the longest worked task?
    • Return the employee with the smallest ID.
  3. Are there any constraints on the values of n and the size of logs?
    • The constraints would be provided in the problem description. Typically, values are constrained to ensure the problem is computable within a reasonable time and space complexity.

Strategy

  1. Initialize variables to keep track of the longest time worked on a single task and the corresponding employee ID.
  2. Iterate through the logs list.
  3. For each log, calculate the time spent on the task by finding the difference between the current timestamp and the previous timestamp.
  4. Keep track of the longest time and update the corresponding employee ID if the current task time is greater than previously recorded longest time. If the times are equal, update only if the current employee ID is smaller.
  5. Return the employee ID with the longest worked task at the end.

Time Complexity

The algorithm primarily involves iterating through the list of logs once, so the time complexity is O(m), where m is the length of the logs list.

Here is an implementation of the solution:

from typing import List

def hardestWorker(n: int, logs: List[List[int]]) -> int:
    max_time = 0
    hardest_worker = None  # Initially, no hardest worker identified
    
    # Starting from first task's completion time
    prev_time = 0  # Beginning with 0 timestamp

    for log in logs:
        emp_id, curr_time = log
        time_spent = curr_time - prev_time
        
        if time_spent > max_time:
            max_time = time_spent
            hardest_worker = emp_id
        elif time_spent == max_time:
            if emp_id < hardest_worker:
                hardest_worker = emp_id
        
        prev_time = curr_time  # Update previous time to current time
    
    return hardest_worker

In this implementation, we:

  1. Initialize max_time as 0 to track the longest task time and hardest_worker as None.
  2. Use prev_time to keep track of the end time of the previous task.
  3. Iterate through logs to calculate the duration of each task and update max_time and hardest_worker accordingly.
  4. Return the ID of the employee who worked the longest on a single task at the end.

Try our interview co-pilot at AlgoAdvance.com