Problem Description

You have n employees, each with a unique ID from 0 to n - 1.

You're given a 2D array logs where each entry logs[i] = [id_i, leaveTime_i] represents:

• id_i: the ID of the employee who worked on the i-th task
• leaveTime_i: the time when the employee finished the i-th task (all leave times are unique)

The important timing rules are:

• The 0-th task starts at time 0
• Each subsequent task starts immediately after the previous one ends
• The i-th task starts right after the (i-1)-th task ends

Your goal is to find the ID of the employee who worked on a single task for the longest duration. If multiple employees have the same longest working time, return the one with the smallest ID.

For example, if logs = [[0,3], [1,5], [0,9]]:

• Employee 0 works on task 0 from time 0 to 3 (duration = 3)
• Employee 1 works on task 1 from time 3 to 5 (duration = 2)
• Employee 0 works on task 2 from time 5 to 9 (duration = 4)

In this case, employee 0 has the longest single task duration of 4, so we return 0.

The solution tracks the end time of the previous task and calculates each task's duration by subtracting the previous end time from the current leave time. It maintains the maximum duration seen and the corresponding employee ID, updating them when a longer duration is found or when the same duration is found with a smaller employee ID.

Intuition

The key insight is that we need to calculate the duration of each task, not just look at the leave times. Since tasks run consecutively without gaps, the duration of task i is simply leaveTime[i] - leaveTime[i-1] (with task 0 starting at time 0).

Think of it like a relay race where each runner starts exactly when the previous one finishes. To find who ran the longest, we need to measure each person's individual segment, not their finish time.

We can solve this in a single pass through the logs by:

1. Keeping track of when the last task ended (initially 0)
2. For each log entry, calculating the task duration as current_leave_time - last_end_time
3. Comparing this duration with our current maximum

The tricky part is handling ties - when two employees have the same maximum duration, we need the one with the smaller ID. This means when we find a duration equal to our current maximum, we should only update our answer if the new employee's ID is smaller.

By maintaining just three variables (last for the previous end time, mx for the maximum duration seen, and ans for the corresponding employee ID), we can efficiently track everything we need in one traversal. Each time we see a new task, we calculate its duration, check if it's a new maximum (or a tie with a better ID), and then update our last time for the next iteration.

This greedy approach works because we only care about the single longest task duration - we don't need to track all durations or sort anything, just keep updating our best answer as we go.

Solution Approach

We implement a direct traversal approach using three variables to track our state:

• last: tracks the end time of the previous task (initialized to 0)
• mx: stores the maximum task duration found so far (initialized to 0)
• ans: stores the employee ID with the maximum duration (initialized to 0)

Let's walk through the implementation step by step:

1. Initialize tracking variables: Start with last = mx = ans = 0. The first task begins at time 0, so last starts at 0.

2. Iterate through each log entry: For each [uid, t] in logs:

   • Calculate the actual task duration: t -= last. This gives us the time spent on this specific task (current leave time minus previous task's end time).

3. Update maximum if needed: Check if we found a better employee:

   • If mx < t: This employee worked longer than any previous one, so update both ans = uid and mx = t
   • If mx == t and ans > uid: This employee worked the same duration as our current maximum but has a smaller ID, so update ans = uid (keeping mx the same)

4. Update the last end time: Add the duration back to last with last += t. This prepares us for the next iteration where we'll need to know when the current task ended.

5. Return the result: After processing all logs, ans contains the ID of the hardest worker.

The algorithm runs in O(m) time where m is the number of logs, with O(1) space complexity since we only use three variables regardless of input size.

Example trace with logs = [[0,3], [1,5], [0,9]]:

• Initially: last=0, mx=0, ans=0
• Process [0,3]: duration = 3-0=3, update mx=3, ans=0, last=3
• Process [1,5]: duration = 5-3=2, no update (2 < 3), last=5
• Process [0,9]: duration = 9-5=4, update mx=4, ans=0, last=9
• Return 0

Example Walkthrough

Let's walk through a small example with logs = [[2,6], [0,8], [2,12], [1,15]].

We'll track three variables:

• last: end time of previous task (starts at 0)
• mx: maximum duration seen so far (starts at 0)
• ans: employee ID with maximum duration (starts at 0)

Step 1: Process [2,6]

• Task duration: 6 - 0 = 6 (task runs from time 0 to 6)
• Since 6 > mx(0), update: mx = 6, ans = 2
• Update last = 6 for next iteration
• State: last=6, mx=6, ans=2

Step 2: Process [0,8]

• Task duration: 8 - 6 = 2 (task runs from time 6 to 8)
• Since 2 < mx(6), no updates to mx or ans
• Update last = 8
• State: last=8, mx=6, ans=2

Step 3: Process [2,12]

• Task duration: 12 - 8 = 4 (task runs from time 8 to 12)
• Since 4 < mx(6), no updates to mx or ans
• Update last = 12
• State: last=12, mx=6, ans=2

Step 4: Process [1,15]

• Task duration: 15 - 12 = 3 (task runs from time 12 to 15)
• Since 3 < mx(6), no updates to mx or ans
• Update last = 15
• Final state: last=15, mx=6, ans=2

Result: Employee 2 worked the longest single task (6 time units), so we return 2.

The key insight is that we're comparing individual task durations, not total work time. Employee 2 appears twice in the logs but we only care about their longest single task, which was their first one with duration 6.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array logs. The algorithm iterates through the logs array exactly once, performing constant-time operations (comparisons, assignments, and arithmetic operations) for each element.

The space complexity is O(1). The algorithm only uses a fixed number of variables (last, mx, ans) to track the state regardless of the input size, requiring constant extra space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Handling Tie-Breaking Logic

The Pitfall: A common mistake is using <= instead of < when comparing durations for the tie-breaking condition. This would incorrectly update the answer even when a later employee with a larger ID has the same duration.

# WRONG - This always updates when durations are equal, even for larger IDs
if max_duration <= current_duration:
    hardest_worker_id = worker_id
    max_duration = current_duration

The Solution: Use the correct compound condition that explicitly checks both cases:

# CORRECT - Only update if duration is greater OR (equal duration AND smaller ID)
if max_duration < current_duration or (max_duration == current_duration and hardest_worker_id > worker_id):
    hardest_worker_id = worker_id
    max_duration = current_duration

2. Misunderstanding Task Start Times

The Pitfall: Assuming each task starts at the previous task's leaveTime instead of understanding that tasks are consecutive. Some might try to track individual start times or create unnecessary complexity.

# WRONG - Overcomplicating by trying to track start times separately
start_times = [0]
for i in range(1, len(logs)):
    start_times.append(logs[i-1][1])

The Solution: Simply track the previous end time and calculate duration as the difference:

# CORRECT - Simple tracking of previous end time
last_end_time = 0
for worker_id, end_time in logs:
    current_duration = end_time - last_end_time
    # ... rest of logic
    last_end_time = end_time

3. Forgetting to Initialize the Answer Variable

The Pitfall: Not initializing hardest_worker_id or initializing it to an invalid value like -1 or n. This causes issues when all tasks have duration 0 or when the first task needs to be the answer.

# WRONG - Invalid initialization
hardest_worker_id = -1  # or hardest_worker_id = n

The Solution: Initialize to a valid worker ID (typically 0):

# CORRECT - Valid initialization
hardest_worker_id = 0

4. Modifying Input Data Instead of Using Local Variables

The Pitfall: Directly modifying the end_time in the logs array, which could cause issues if the array needs to be reused or in languages where modifications affect the original data.

# WRONG - Modifying input data
for i in range(len(logs)):
    logs[i][1] -= last_end_time  # Modifying original data
    # ... rest of logic

The Solution: Use local variables to store calculated values:

# CORRECT - Using local variable
for worker_id, end_time in logs:
    current_duration = end_time - last_end_time  # Local calculation
    # ... rest of logic