# The Employee That Worked on the Longest Task
**Difficulty:** EASY
[External](https://leetcode.com/problems/the-employee-that-worked-on-the-longest-task)
Canonical: https://scaleengineer.com/dsa/problems/the-employee-that-worked-on-the-longest-task
**Data structures:** Array
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley)
---
## Problem
There are `n` employees, each with a unique id from `0` to `n - 1`.

You are given a 2D integer array `logs` where `logs[i] = [idi, leaveTimei]` where:

* `idi` is the id of the employee that worked on the `ith` task, and
* `leaveTimei` is the time at which the employee finished the `ith` task. All the values `leaveTimei` are **unique**.

Note that the `ith` task starts the moment right after the `(i - 1)th` task ends, and the `0th` task starts at time `0`.

Return _the id of the employee that worked the task with the longest time._ If there is a tie between two or more employees, return _the **smallest** id among them_.

**Example 1:**

**Input:** n = 10, logs = [[0,3],[2,5],[0,9],[1,15]]
**Output:** 1
**Explanation:** 
Task 0 started at 0 and ended at 3 with 3 units of times.
Task 1 started at 3 and ended at 5 with 2 units of times.
Task 2 started at 5 and ended at 9 with 4 units of times.
Task 3 started at 9 and ended at 15 with 6 units of times.
The task with the longest time is task 3 and the employee with id 1 is the one that worked on it, so we return 1.

**Example 2:**

**Input:** n = 26, logs = [[1,1],[3,7],[2,12],[7,17]]
**Output:** 3
**Explanation:** 
Task 0 started at 0 and ended at 1 with 1 unit of times.
Task 1 started at 1 and ended at 7 with 6 units of times.
Task 2 started at 7 and ended at 12 with 5 units of times.
Task 3 started at 12 and ended at 17 with 5 units of times.
The tasks with the longest time is task 1. The employee that worked on it is 3, so we return 3.

**Example 3:**

**Input:** n = 2, logs = [[0,10],[1,20]]
**Output:** 0
**Explanation:** 
Task 0 started at 0 and ended at 10 with 10 units of times.
Task 1 started at 10 and ended at 20 with 10 units of times.
The tasks with the longest time are tasks 0 and 1. The employees that worked on them are 0 and 1, so we return the smallest id 0.

**Constraints:**

* `2 <= n <= 500`
* `1 <= logs.length <= 500`
* `logs[i].length == 2`
* `0 <= idi <= n - 1`
* `1 <= leaveTimei <= 500`
* `idi != idi+1`
* `leaveTimei` are sorted in a strictly increasing order.

# Approaches
## Two Passes with Extra Space
This approach involves two main steps. First, we iterate through the `logs` array to calculate the duration of each task and store these durations along with the corresponding employee IDs in an auxiliary data structure. In the second step, we iterate through this new data structure to find the maximum duration and the associated employee ID, handling ties by choosing the smallest ID.
**Time:** O(L), where L is the number of logs. The first loop to calculate durations takes O(L) time, and the second loop to find the maximum also takes O(L) time. The total time complexity is O(L) + O(L) = O(L). · **Space:** O(L), where L is the number of logs. We use an auxiliary list to store the duration and employee ID for each of the L tasks.
**Pros:** Conceptually simple and easy to break down into two distinct steps.; Separates the logic of calculating durations from finding the maximum, which can make the code easier to read for some.
**Cons:** Uses extra space proportional to the number of logs, which is unnecessary.; Requires two separate loops over the data, making it slightly less performant than a single-pass solution.
### Explanation
We can solve this problem by first processing all the logs to determine the duration of each individual task. We'll create a list to hold pairs of `(duration, employeeId)`. We iterate through the `logs` array, calculating each task's duration. The duration of the first task is its `leaveTime`. For subsequent tasks, the duration is the difference between its `leaveTime` and the `leaveTime` of the previous task. After computing all durations, we perform a second pass over our list of `(duration, employeeId)` pairs. During this second pass, we keep track of the longest duration seen so far and the ID of the employee who worked that task. If we find a task with a duration equal to the current maximum, we update the result to be the smaller of the two employee IDs, as required by the problem statement.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    // A helper class to store task details
    class TaskDetail {
        int duration;
        int employeeId;
        TaskDetail(int duration, int employeeId) {
            this.duration = duration;
            this.employeeId = employeeId;
        }
    }

    public int hardestWorker(int n, int[][] logs) {
        List<TaskDetail> taskDetails = new ArrayList<>();
        int startTime = 0;

        // First pass: calculate and store all task durations
        for (int[] log : logs) {
            int employeeId = log[0];
            int leaveTime = log[1];
            int duration = leaveTime - startTime;
            taskDetails.add(new TaskDetail(duration, employeeId));
            startTime = leaveTime;
        }

        // Second pass: find the employee with the longest task
        int maxDuration = -1;
        int resultId = -1;

        for (TaskDetail task : taskDetails) {
            if (task.duration > maxDuration) {
                maxDuration = task.duration;
                resultId = task.employeeId;
            } else if (task.duration == maxDuration) {
                resultId = Math.min(resultId, task.employeeId);
            }
        }

        return resultId;
    }
}
```
### Algorithm
- Create a list, say `taskDetails`, to store pairs of (duration, employee ID).
- Initialize a variable `startTime = 0`.
- Iterate through each `log` in the `logs` array:
    - Get the `employeeId` and `leaveTime` from the current `log`.
    - Calculate `duration = leaveTime - startTime`.
    - Add the pair `(duration, employeeId)` to `taskDetails`.
    - Update `startTime = leaveTime`.
- Initialize `maxDuration = -1` and `resultId = -1`.
- Iterate through each pair `(duration, employeeId)` in `taskDetails`:
    - If `duration > maxDuration`:
        - Update `maxDuration = duration`.
        - Update `resultId = employeeId`.
    - Else if `duration == maxDuration`:
        - Update `resultId = min(resultId, employeeId)`.
- Return `resultId`.

## Single Pass with Constant Space
This is the most efficient approach. We can determine the employee who worked the longest task by iterating through the `logs` array just once. We maintain variables to track the maximum duration found so far and the ID of the corresponding employee. As we iterate, we calculate the duration of the current task and update our tracking variables if we find a new longest task or a tie with a smaller employee ID.
**Time:** O(L), where L is the number of logs. We iterate through the `logs` array exactly once. · **Space:** O(1). We only use a few variables to store the maximum duration, the result ID, and the last leave time, regardless of the input size.
**Pros:** Highly efficient in both time and space.; Requires only a single pass through the input data.; Uses constant extra space, making it suitable for large inputs.
**Cons:** Combines calculation and comparison in a single loop, which might be slightly less modular, though it's simple enough not to be a major issue.
### Explanation
This optimal solution avoids using any extra space by processing the logs in a single pass. We can calculate the duration of each task and compare it with the maximum duration found so far on the fly. We initialize variables to keep track of the result: `maxDuration` to store the longest duration and `resultId` for the employee's ID. We also need a variable, say `lastLeaveTime`, to store the end time of the previous task, which is the start time for the current task. `lastLeaveTime` is initialized to 0 for the first task. We iterate through the `logs` array. In each iteration, we calculate the current task's duration by subtracting `lastLeaveTime` from the current task's `leaveTime`. We then compare this `currentDuration` with `maxDuration`. If `currentDuration` is greater than `maxDuration`, we've found a new longest task. We update `maxDuration` with `currentDuration` and `resultId` with the current employee's ID. If `currentDuration` is equal to `maxDuration`, we have a tie. The problem requires us to choose the employee with the smaller ID, so we update `resultId` to be the minimum of its current value and the current employee's ID. After the loop, `resultId` will hold the ID of the employee who worked the longest task, with ties broken correctly.

```java
class Solution {
    public int hardestWorker(int n, int[][] logs) {
        int maxDuration = 0;
        int resultId = -1;
        int lastLeaveTime = 0;

        for (int[] log : logs) {
            int employeeId = log[0];
            int leaveTime = log[1];
            int currentDuration = leaveTime - lastLeaveTime;

            if (currentDuration > maxDuration) {
                maxDuration = currentDuration;
                resultId = employeeId;
            } else if (currentDuration == maxDuration) {
                // If durations are equal, choose the employee with the smaller id.
                resultId = Math.min(resultId, employeeId);
            }
            
            // Update the start time for the next task.
            lastLeaveTime = leaveTime;
        }
        return resultId;
    }
}
```
### Algorithm
- Initialize `maxDuration = 0`.
- Initialize `resultId = -1`.
- Initialize `lastLeaveTime = 0`.
- Iterate through each `log` in the `logs` array:
    - Get the `employeeId` and `leaveTime` from the current `log`.
    - Calculate `currentDuration = leaveTime - lastLeaveTime`.
    - If `currentDuration > maxDuration`:
        - Update `maxDuration = currentDuration`.
        - Update `resultId = employeeId`.
    - Else if `currentDuration == maxDuration`:
        - Update `resultId = min(resultId, employeeId)`.
    - Update `lastLeaveTime = leaveTime`.
- Return `resultId`.

# Solutions
### Java

```java
class Solution {
public
  int hardestWorker(int n, int[][] logs) {
    int ans = 0;
    int last = 0, mx = 0;
    for (int[] log : logs) {
      int uid = log[0], t = log[1];
      t -= last;
      if (mx < t || (mx == t && ans > uid)) {
        ans = uid;
        mx = t;
      }
      last += t;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int hardestWorker(int n, vector<vector<int>> &logs) {
    int ans = 0, mx = 0, last = 0;
    for (auto &log : logs) {
      int uid = log[0], t = log[1];
      t -= last;
      if (mx < t || (mx == t && ans > uid)) {
        mx = t;
        ans = uid;
      }
      last += t;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def hardestWorker(self, n: int, logs: List[List[int]]) -> int: last = mx = ans = 0 for uid, t in logs: t -= last if mx < t or (mx == t and ans > uid): ans, mx = uid, t last += t return ans

```