The Employee That Worked on the Longest Task

Easy

Asked by:

7 views

Topics:

Arrays

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] = [id_i, leaveTime_i] where:

id_i is the id of the employee that worked on the i^th task, and
leaveTime_i is the time at which the employee finished the i^th task. All the values leaveTime_i are unique.

Note that the i^th task starts the moment right after the (i - 1)^th task ends, and the 0^th 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 <= id_i <= n - 1
1 <= leaveTime_i <= 500
id_i != id_i+1
leaveTime_i are sorted in a strictly increasing order.

Try coding it in LeetCode

The Employee That Worked on the Longest Task

Easy

Asked by:

7 views

Topics:

Arrays

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] = [id_i, leaveTime_i] where:

id_i is the id of the employee that worked on the i^th task, and
leaveTime_i is the time at which the employee finished the i^th task. All the values leaveTime_i are unique.

Note that the i^th task starts the moment right after the (i - 1)^th task ends, and the 0^th 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 <= id_i <= n - 1
1 <= leaveTime_i <= 500
id_i != id_i+1
leaveTime_i are sorted in a strictly increasing order.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on `n` and the length of `logs`? What is the maximum possible value for `leaveTime_i` and `id_i`?
Is the `leaveTime_i` in the logs array guaranteed to be monotonically increasing, or do I need to account for unsorted leave times?
Could the `logs` array be empty? If so, what value should I return?
Can multiple employees have the same `leaveTime_i`? If so, how should I handle this scenario?
If there's a tie for the longest task (same duration), should I return the smallest `id` based on numeric value, or some other ordering?

Brute Force Solution

Approach

To find the employee who worked on the longest task using brute force, we check each employee's task durations one by one. We compare these durations to find the largest one. This is like checking every possible answer to find the best one.

Here's how the algorithm would work step-by-step:

Start by looking at the first employee and how long they worked on their task.
Remember this duration as the longest duration we've seen so far, and note that this employee is currently the employee with the longest task.
Now, look at the next employee and their task duration.
Compare this new duration to the longest duration we remembered.
If this new duration is longer than the one we remembered, then replace the remembered duration with this new one, and note that this new employee is now the employee with the longest task.
Keep doing this for all the employees, comparing each employee's task duration to the longest duration we've remembered.
After checking all employees, the employee we noted as having the longest task at the very end is the employee who worked on the longest task.

Code Implementation

def find_employee_with_longest_task(tasks):
    employee_times = {}

    for task in tasks:
        employee_id = task[0]
        start_time = task[1]
        end_time = task[2]

        # Calculate task duration for the current employee
        task_duration = end_time - start_time

        # If employee not yet in dictionary, add them
        if employee_id not in employee_times:
            employee_times[employee_id] = 0

        employee_times[employee_id] += task_duration

    employee_with_longest_task = None
    longest_time = 0

    # Determine employee with the longest time working on tasks.
    for employee_id, total_time in employee_times.items():
        if total_time > longest_time:

            #Store the employee ID and their total time working
            employee_with_longest_task = employee_id
            longest_time = total_time

    return employee_with_longest_task

Big(O) Analysis

Time Complexity

O(n) – The described approach iterates through each employee's task duration once. The input size, n, represents the number of employees. For each employee, a single comparison is made to the current longest duration. Therefore, the number of operations scales linearly with the number of employees, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm maintains only two variables: one to store the longest duration seen so far and another to store the corresponding employee. These variables use a constant amount of space, irrespective of the number of employees. No additional data structures that scale with the input size (N, the number of employees) are used. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

To find the employee who worked on the longest task, we'll go through each employee's tasks and calculate the duration of each task. Then, we'll keep track of the employee with the longest single task duration found so far, updating it whenever we find a longer one.

Here's how the algorithm would work step-by-step:

Start by looking at the records of the first employee.
For each task the employee worked on, subtract the start time from the end time to find out how long that task took.
Compare the length of this task with the length of the longest task we've seen so far.
If the current task is longer than the longest one we've found, remember this employee and the length of this task.
Move on to the next employee and repeat the process of finding the duration of each task and comparing it to the current longest task.
Keep doing this until you've checked all employees and all their tasks.
The employee and task duration you've remembered at the end is the employee who worked on the longest task and the duration of that task.

Code Implementation

def find_employee_with_longest_task(tasks):
    longest_task_duration = 0
    employee_with_longest_task = None

    for task in tasks:
        employee_id = task['employee_id']
        task_duration = task['duration']

        # Update if current task is longer.
        if task_duration > longest_task_duration:

            longest_task_duration = task_duration

            employee_with_longest_task = employee_id

    # After iterating, return the employee ID and max duration.
    return employee_with_longest_task, longest_task_duration

def find_employee_with_longest_task_alternative(tasks):
    max_duration = 0
    employee_id_with_max_duration = None

    for task in tasks:
        current_employee_id = task['employee_id']
        current_duration = task['duration']

        # Core logic: Compare the current duration.
        if current_duration > max_duration:

            # Update the maximum duration.
            max_duration = current_duration

            # Save the employee ID with max duration.
            employee_id_with_max_duration = current_employee_id

    # Return the final result.
    return employee_id_with_max_duration, max_duration

Big(O) Analysis

Time Complexity

O(E) – The provided solution iterates through each employee and then iterates through each of their tasks. Let E be the total number of tasks across all employees. The outer loop implicitly iterates through employees, and the inner loop iterates through the tasks for each employee. The dominant operation is calculating the task duration and comparing it with the maximum duration seen so far, which happens for each task. Therefore, the time complexity is O(E), where E is the total number of employee task entries.

Space Complexity

O(1) – The algorithm uses only a few variables to store the current longest task duration and the corresponding employee. These variables (longest duration, employee ID) take up constant space regardless of the number of employees or tasks. Therefore, the auxiliary space required does not depend on the input size (N) and remains constant. The space complexity is O(1).

Edge Cases

Case	How to Handle
Empty logs array	Return -1 since there are no tasks to consider.
Null logs array	Return -1 or throw an IllegalArgumentException to signal invalid input.
n is 0 or negative, but logs is not empty	Handle this by either ignoring n and processing the logs, or throw an IllegalArgumentException if n is required for processing.
Logs contains only one task	Return the employee ID of that single task since it is the longest.
Logs contains tasks with the same duration but different employee IDs	The solution should iterate through the logs and keep track of the longest duration and the smallest ID among those with the longest duration.
Large leaveTime values potentially leading to integer overflow when calculating duration if not handled carefully	Use long data type for duration calculation to prevent potential overflow.
Logs are not sorted by leaveTime	The solution must correctly calculate duration using the previous leaveTime or assume a starting time of 0 and process correctly.
Duplicate employee IDs with differing leave times	The algorithm correctly updates the last leave time of the specified employee based on the given employee ID if necessary.