Easy

题目描述

有 n 个员工，每个员工都有一个从 0 到 n - 1 的唯一 id。

给你一个二维整数数组 logs，其中 logs[i] = [idi, leaveTimei]：

  • idi 是完成第 i 个任务的员工的 id
  • leaveTimei 是员工完成第 i 个任务的时刻。所有 leaveTimei 的值都是唯一的。

注意第 i 个任务在第 (i - 1) 个任务结束的那一刻开始，第 0 个任务在时刻 0 开始。

返回完成任务用时最长的员工的 id。如果两个或多个员工完成任务的用时相同，返回其中 id 最小的。

示例 1：

输入：n = 10, logs = [[0,3],[2,5],[0,9],[1,15]]
输出：1
解释：
任务 0 从 0 开始，到 3 结束，用时 3。
任务 1 从 3 开始，到 5 结束，用时 2。
任务 2 从 5 开始，到 9 结束，用时 4。
任务 3 从 9 开始，到 15 结束，用时 6。
用时最长的是任务 3，员工 id 为 1，所以返回 1。

示例 2：

输入：n = 26, logs = [[1,1],[3,7],[2,12],[7,17]]
输出：3

示例 3：

输入：n = 2, logs = [[0,10],[1,20]]
输出：0

提示：

  • 2 <= n <= 500
  • 1 <= logs.length <= 500
  • logs[i].length == 2
  • 0 <= idi <= n - 1
  • 1 <= leaveTimei <= 500
  • idi != idi+1
  • leaveTimei 按严格递增顺序排列

解题思路

解题思路

这道题要求找到完成任务用时最长的员工。我们需要计算每个任务的执行时间，然后找出最长时间对应的员工。

思路分析：

  1. 计算任务执行时间：第 i 个任务的执行时间 = logs[i][1] - logs[i-1][1]（第一个任务从时间0开始）

  2. 记录最长时间和对应员工：遍历所有任务，维护当前最长执行时间和对应的员工ID

  3. 处理相同时间的情况：当出现相同的最长时间时，选择ID较小的员工

具体步骤：

  • 初始化最长时间为第一个任务的时间（logs[0][1]）
  • 遍历后续任务，计算每个任务的执行时间
  • 如果当前任务时间更长，或者时间相同但员工ID更小，则更新结果
  • 返回最终的员工ID

时间复杂度： O(m)，其中 m 是 logs 的长度 空间复杂度： O(1)

代码实现

class Solution {
public:
    int hardestWorker(int n, vector<vector<int>>& logs) {
        int maxTime = logs[0][1];
        int result = logs[0][0];
        
        for (int i = 1; i < logs.size(); i++) {
            int taskTime = logs[i][1] - logs[i-1][1];
            if (taskTime > maxTime || (taskTime == maxTime && logs[i][0] < result)) {
                maxTime = taskTime;
                result = logs[i][0];
            }
        }
        
        return result;
    }
};

class Solution:
    def hardestWorker(self, n: int, logs: List[List[int]]) -> int:
        max_time = logs[0][1]
        result = logs[0][0]
        
        for i in range(1, len(logs)):
            task_time = logs[i][1] - logs[i-1][1]
            if task_time > max_time or (task_time == max_time and logs[i][0] < result):
                max_time = task_time
                result = logs[i][0]
        
        return result

public class Solution {
    public int HardestWorker(int n, int[][] logs) {
        int maxTime = logs[0][1];
        int result = logs[0][0];
        
        for (int i = 1; i < logs.Length; i++) {
            int taskTime = logs[i][1] - logs[i-1][1];
            if (taskTime > maxTime || (taskTime == maxTime && logs[i][0] < result)) {
                maxTime = taskTime;
                result = logs[i][0];
            }
        }
        
        return result;
    }
}

var hardestWorker = function(n, logs) {
    let maxTime = logs[0][1];
    let result = logs[0][0];
    
    for (let i = 1; i < logs.length; i++) {
        let taskTime = logs[i][1] - logs[i-1][1];
        if (taskTime > maxTime || (taskTime === maxTime && logs[i][0] < result)) {
            maxTime = taskTime;
            result = logs[i][0];
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
一次遍历O(m)O(1)

其中 m 是 logs 数组的长度。