The Employee That Worked on the Longest Task

Easy
1073.

The Employee That Worked on the Longest Task

The Employee That Worked on the Longest Task is an easy coding problem on arrays, asked in Amazon, Google, Wipro and Morgan Stanley interviews.

There are n employees, numbered 0 to n - 1. logs[i] = [id, leaveTime] records that employee id finished a task at leaveTime. The logs are sorted by leaveTime, tasks run back to back, and the first task started at time 0.

Return the id of the employee whose single task took the longest. On a tie, return the smallest id.

Example 1

Input
n = 10, logs = [[0,3],[2,5],[0,9],[1,15]]
Output
1
Explanation
The durations are 3, 2, 4 and 6; the 6 belongs to employee 1.

Example 2

Input
n = 26, logs = [[1,1],[3,7],[2,12],[7,17]]
Output
3
Explanation
Durations 1, 6, 5 and 5 — employee 3 worked 6.

Example 3

Input
n = 2, logs = [[0,10],[1,20]]
Output
0
Explanation
Both worked 10; the smaller id wins.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} logs
 * @return {number}
 */
var hardestWorker = function(n, logs) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

The Employee That Worked on the Longest Task — Solution

The Employee That Worked on the Longest Task solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

The Employee That Worked on the Longest Task is an easy coding problem on arrays, asked in Amazon, Google, Wipro and Morgan Stanley interviews.

  • Difficulty: Easy
  • Topics: Arrays
  • Asked at: Amazon, Google, Wipro, Morgan Stanley
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

There are n employees, numbered 0 to n - 1. logs[i] = [id, leaveTime] records that employee id finished a task at leaveTime. The logs are sorted by leaveTime, tasks run back to back, and the first task started at time 0.

Return the id of the employee whose single task took the longest. On a tie, return the smallest id.

Example 1

Input: n = 10, logs = [[0,3],[2,5],[0,9],[1,15]]
Output: 1
Explanation: The durations are 3, 2, 4 and 6; the 6 belongs to employee 1.

Example 2

Input: n = 26, logs = [[1,1],[3,7],[2,12],[7,17]] 
Output: 3
Explanation: Durations 1, 6, 5 and 5 — employee 3 worked 6.

Example 3

Input: n = 2, logs = [[0,10],[1,20]]
Output: 0
Explanation: Both worked 10; the smaller id wins.

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.

Hints for The Employee That Worked on the Longest Task

  1. Hint 1

    A task's duration is the gap between its own leave time and the previous one.

  2. Hint 2

    The very first task started at 0, so its duration is its leave time.

  3. Hint 3

    Track the longest duration and break ties toward the smaller id.

How to solve The Employee That Worked on the Longest Task

Each log entry's task duration is leaveTime[i] - leaveTime[i-1], with the first task measured from 0. One pass keeps the longest and applies the tie-break.

Approach

  1. Seed the answer with the first log: duration logs[0][1], id logs[0][0].
  2. For each later entry, compute the gap from the previous leave time.
  3. Replace the best when the gap is longer, or equal with a smaller id.

Why it works

The "tasks run back to back" wording is what makes the gap the duration — there is no idle time to account for, so no start times are needed. The tie-break must be checked on every equal duration, not only the first, which is the single place a one-pass loop usually goes wrong here.

Complexity

  • Time — O(m)
  • Space — O(1)

Pitfalls

  • The first task's duration is its leave time, not zero.
  • The smallest id wins a tie, not the earliest task.
  • n is only there to bound the ids; it plays no part in the computation.

Reference solution

Python

from typing import List

def hardestWorker(n: int, logs: List[List[int]]) -> int:
    best, best_time = logs[0][0], logs[0][1]
    for i in range(1, len(logs)):
        span = logs[i][1] - logs[i - 1][1]
        if span > best_time or (span == best_time and logs[i][0] < best):
            best, best_time = logs[i][0], span
    return best

Java

public static int hardestWorker(int n, int[][] logs) {
    int best = logs[0][0], bestTime = logs[0][1];
    for (int i = 1; i < logs.length; i++) {
        int span = logs[i][1] - logs[i - 1][1];
        if (span > bestTime || (span == bestTime && logs[i][0] < best)) {
            best = logs[i][0];
            bestTime = span;
        }
    }
    return best;
}

C++

int hardestWorker(int n, vector<vector<int>>& logs) {
    int best = logs[0][0], bestTime = logs[0][1];
    for (int i = 1; i < (int) logs.size(); i++) {
        int span = logs[i][1] - logs[i - 1][1];
        if (span > bestTime || (span == bestTime && logs[i][0] < best)) {
            best = logs[i][0];
            bestTime = span;
        }
    }
    return best;
}

JavaScript

var hardestWorker = function(n, logs) {
    var best = logs[0][0], bestTime = logs[0][1];
    for (var i = 1; i < logs.length; i++) {
        var span = logs[i][1] - logs[i - 1][1];
        if (span > bestTime || (span === bestTime && logs[i][0] < best)) {
            best = logs[i][0];
            bestTime = span;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays