The Employee That Worked on the Longest Task

🏠 ⬅️ ➡️

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 employees 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.
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: n, i, j, id, leaveTime, maxLeaveTime, maxId
    integer, allocatable :: logs(:, :)

    ! read input
    read(*, *) n
    allocate(logs(n, 2))
    do i = 1, n
        read(*, *) logs(i, :)
    end do

    ! solve problem
    maxLeaveTime = 0
    maxId = 0
    do i = 1, n
        id = logs(i, 1)
        leaveTime = logs(i, 2)
        if (leaveTime > maxLeaveTime) then
            maxLeaveTime = leaveTime
            maxId = id
        elseif (leaveTime == maxLeaveTime .and. id < maxId) then
            maxId = id
        end if
    end do

    ! print output
    write (*, '(I0)') maxId

end program main
❌ Compiled
❌ Executed
❌ Correct 
module m_longest_task

  implicit none

contains

  function longest_task(n, logs) result(employee_id)
    integer, intent(in) :: n
    integer, intent(in) :: logs(n, 2)
    integer :: employee_id
    integer :: i, j, id, leave_time, max_leave_time, max_id

    ! Initialize variables
    max_leave_time = 0
    max_id = 0

    ! Iterate over the logs
    do i = 1, n
      id = logs(i, 1)
      leave_time = logs(i, 2)

      ! If the leave time is greater than the current max leave time,
      ! update the max leave time and the employee id
      if (leave_time > max_leave_time) then
        max_leave_time = leave_time
        max_id = id
      end if
    end do

    ! Return the employee id with the longest leave time
    employee_id = max_id

  end function longest_task

end module m_longest_task

program p_longest_task
  use m_longest_task
  implicit none

  ! Test case 1
  print *, longest_task(10, &
      reshape([0, 3, 2, 5, 0, 9, 1, 15], [7, 2]))

  ! Test case 2
  print *, longest_task(26, &
      reshape([1, 1, 3, 7, 2, 12, 7, 17], [8, 2]))

  ! Test case 3
  print *, longest_task(2, &
      reshape([0, 10, 1, 20], [4, 2]))

end program p_longest_task
🌐 Data from online sources 
def worker_with_longest_task(n, logs):
    result = 0
    max_time = logs[0][1] - 0

    for i in range(1, len(logs)):
        time = logs[i][1] - logs[i-1][1]
        if time > max_time:
            max_time = time
            result = logs[i][0]

    return result

The algorithm iterates through the array logs one task at a time. For each task, the algorithm computes the time it took to complete the task by subtracting the leave time of the previous task from the leave time of the current task. We initialize the max_time with the first task duration and set the result to the ID of the first task worker.

During iteration, if the computed time for the current task is greater than the max_time, the algorithm updates the max_time to the current task's time and selects the worker of the current task as result.

After iterating through all tasks, the algorithm returns the worker ID in result, which is the worker that worked the task with the longest time. If there is a tie, the algorithm will return the smallest ID among them since we only update the result when we find a strictly greater time.

🌐 Data from online sources 
int workerWithLongestTask(int n, vector<vector<int>>& logs) {
    int result = 0;
    int max_time = logs[0][1] - 0;

    for (int i = 1; i < logs.size(); ++i) {
        int time = logs[i][1] - logs[i-1][1];
        if (time > max_time) {
            max_time = time;
            result = logs[i][0];
        }
    }
    return result;
}

The algorithm iterates through the array logs one task at a time. For each task, the algorithm computes the time it took to complete the task by subtracting the leave time of the previous task from the leave time of the current task. We initialize the max_time with the first task duration and set the result to the ID of the first task worker.

During iteration, if the computed time for the current task is greater than the max_time, the algorithm updates the max_time to the current task's time and selects the worker of the current task as result.

After iterating through all tasks, the algorithm returns the worker ID in result, which is the worker that worked the task with the longest time. If there is a tie, the algorithm will return the smallest ID among them since we only update the result when we find a strictly greater time.