LeetCode 2432 - The Employee That Worked on the Longest Task

LeetCode Problem 2432

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem asks us to identify which employee worked the task with the longest duration given a sequence of tasks completed by employees. Each task is represented in logs[i] = [idi, leaveTimei], where idi is the employee id and leaveTimei is the time the task was completed. The start time of each task is implicitly defined: the first task starts at 0 and each subsequent task starts immediately after the previous task ends. The employee that worked the task with the maximum duration should be returned, and in case of ties, the smallest employee id should be returned.

The input constraints are small: n and logs.length are at most 500. All leaveTimei values are unique and strictly increasing, and consecutive tasks are worked on by different employees. This guarantees that each task has a positive duration and that there are no ambiguities in task ordering. Edge cases include multiple tasks sharing the maximum duration or the first or last task being the longest.

Approaches

A naive approach would explicitly calculate the duration of each task and store all durations in a list, then search for the maximum duration and retrieve the corresponding employee id. This is correct but requires a separate traversal and extra space, which is unnecessary since we can track the maximum dynamically.

The optimal approach leverages the fact that task durations can be computed on the fly and we only need the current maximum. We iterate through the logs, compute the task duration for each task by subtracting the previous task's leave time (or 0 for the first task), and maintain a record of the maximum duration and corresponding employee id. If multiple tasks have the same maximum duration, we update the id only if the current employee id is smaller. This method is linear in time and uses constant extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Stores all task durations explicitly and searches for max
Optimal	O(n)	O(1)	Tracks maximum duration and corresponding employee id on the fly

Algorithm Walkthrough

1. Initialize max_duration to 0 and hardest_employee to 0. These will track the longest task duration and the corresponding employee id.

2. Initialize prev_time to 0. This variable represents the end time of the previous task and is used to compute the current task's duration.

3. Iterate over each task in logs. For each task:

4. Compute the task duration as duration = leaveTimei - prev_time.

5. If duration > max_duration, update max_duration = duration and hardest_employee = idi.

6. If duration == max_duration and idi < hardest_employee, update hardest_employee = idi to handle ties.

7. Update prev_time = leaveTimei for the next iteration.

8. After iterating through all tasks, return hardest_employee.

Why it works: The algorithm maintains the invariant that hardest_employee always represents the employee who has completed the task with the maximum duration so far. Since each task's duration is uniquely determined by consecutive leave times, this guarantees correctness. Ties are resolved by comparing employee ids at the moment of equality.

Python Solution

from typing import List

class Solution:
    def hardestWorker(self, n: int, logs: List[List[int]]) -> int:
        max_duration = 0
        hardest_employee = 0
        prev_time = 0

        for emp_id, leave_time in logs:
            duration = leave_time - prev_time
            if duration > max_duration or (duration == max_duration and emp_id < hardest_employee):
                max_duration = duration
                hardest_employee = emp_id
            prev_time = leave_time

        return hardest_employee

Explanation: We initialize tracking variables and iterate through each log. For each task, we compute the duration relative to the previous task’s finish time. Whenever a longer duration is found, we update both max_duration and hardest_employee. If the duration ties with the current maximum, we ensure the employee with the smaller id is selected. The final value of hardest_employee is returned.

Go Solution

func hardestWorker(n int, logs [][]int) int {
    maxDuration := 0
    hardestEmployee := 0
    prevTime := 0

    for _, log := range logs {
        empID := log[0]
        leaveTime := log[1]
        duration := leaveTime - prevTime
        if duration > maxDuration || (duration == maxDuration && empID < hardestEmployee) {
            maxDuration = duration
            hardestEmployee = empID
        }
        prevTime = leaveTime
    }

    return hardestEmployee
}

Explanation: The Go solution mirrors the Python approach. Slices are used to access log entries, and variables maxDuration, hardestEmployee, and prevTime track the same information. Ties are resolved by comparing employee ids in the same way. No additional memory is used beyond a few integers.

Worked Examples

Example 1:

Task	emp_id	leave_time	prev_time	duration	max_duration	hardest_employee
0	0	3	0	3	3	0
1	2	5	3	2	3	0
2	0	9	5	4	4	0
3	1	15	9	6	6	1

Result: 1

Example 2:

Task	emp_id	leave_time	prev_time	duration	max_duration	hardest_employee
0	1	1	0	1	1	1
1	3	7	1	6	6	3
2	2	12	7	5	6	3
3	7	17	12	5	6	3

Result: 3

Example 3:

Task	emp_id	leave_time	prev_time	duration	max_duration	hardest_employee
0	0	10	0	10	10	0
1	1	20	10	10	10	0

Result: 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through the logs array once, computing durations on the fly.
Space	O(1)	Only a few integer variables are used regardless of input size.

The linear time complexity is efficient given the constraints (n and logs.length ≤ 500). Constant space ensures minimal memory usage.

Test Cases

# Provided examples
assert Solution().hardestWorker(10, [[0,3],[2,5],[0,9],[1,15]]) == 1  # Longest task 6 by emp 1
assert Solution().hardestWorker(26, [[1,1],[3,7],[2,12],[7,17]]) == 3  # Longest task 6 by emp 3
assert Solution().hardestWorker(2, [[0,10],[1,20]]) == 0  # Tie duration, smaller id

# Edge cases
assert Solution().hardestWorker(2, [[1,1],[0,2]]) == 0  # First task smaller, second longer
assert Solution().hardestWorker(3, [[2,2],[1,5],[0,7]]) == 1  # Middle task longest
assert Solution().hardestWorker(4, [[0,2],[1,4],[2,6],[3,8]]) == 0  # All durations equal, smallest id
assert Solution().hardestWorker(5, [[4,1],[3,3],[2,6],[1,10],[0,15]]) == 0  # Last task longest

Test	Why
Example 1	Basic functionality with varying durations
Example 2	Longest task in the middle
Example 3	Tie in duration between first and last task
First task smaller, second longer	Checks dynamic update of longest task
Middle task longest	Validates proper handling of max in middle
All equal durations	Ensures tie resolution by smallest id
Last task longest	Confirms last task is properly considered

Edge Cases

Tie for longest duration: If multiple tasks share the same maximum duration, the smallest employee id should be returned. This could trip up naive implementations that only track the last occurrence. Our algorithm explicitly checks for ties and updates the employee id accordingly.

**First or last task