题目描述

力扣公司的员工都使用员工卡来开办公室的门。每当一个员工使用一次他的员工卡，安保系统会记录下员工的名字和使用时间。如果一个员工在一小时时间内使用员工卡的次数大于等于三次，这个系统会自动发布一个 警告。

给定字符串数组 keyName 和 keyTime，其中 [keyName[i], keyTime[i]] 对应一个人的名字和他在 某一天 内使用员工卡的时间。

使用时间的格式是 24小时制，形如 “HH:MM”，比方说 “23:51” 和 “09:49”。

请你返回去重后的收到系统警告的员工名字，将它们按 字典序升序 排序后返回。

请注意 "10:00" - "11:00" 视为一个小时时间范围内，而 "23:51" - "00:10" 不被视为一小时内，因为系统记录的是某一天内的使用情况。

样例

输入：
keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"]
keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
输出：["daniel"]
解释："daniel" 在一小时内使用了 3 次员工卡（"10:00"，"10:40"，"11:00"）。

输入：
keyName = ["alice","alice","alice","bob","bob","bob","bob"]
keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
输出：["bob"]
解释："bob" 在一小时内使用了 3 次员工卡（"21:00"，"21:20"，"21:30"）。

输入：
keyName = ["john","john","john"]
keyTime = ["23:58","23:59","00:01"]
输出：[]

输入：
keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"]
keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"]
输出：["clare","leslie"]

限制

• 1 <= keyName.length, keyTime.length <= 10^5
• keyName.length == keyTime.length
• keyTime 格式为 “HH:MM”。
• 保证 [keyName[i], keyTime[i]] 形成的二元对 互不相同。
• 1 <= keyName[i].length <= 10
• keyName[i] 只包含小写英文字母。

算法

(哈希表，排序) $O(n \log n)$

1. 用哈希表记录每个人在这一天的所有时间点。
2. 对于每个人，排序其所有时间点，然后遍历查看是否存在三个连续的时间点，其间隔小于等于 60 分钟。
3. 最后排序所有被警告的人名。

时间复杂度

• 最坏情况下，需要排序一次所有的时间点，故时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储每个人的所有时间点和答案。

C++ 代码

class Solution {
public:
    vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
        unordered_map<string, vector<int>> used;
        const int n = keyName.size();
        for (int i = 0; i < n; i++) {
            int hh, mm;
            sscanf(keyTime[i].c_str(), "%d:%d", &hh, &mm);
            used[keyName[i]].push_back(hh*60 + mm);
        }

        vector<string> ans;
        for (auto person : used) {
            vector<int> &ts = person.second;

            sort(ts.begin(), ts.end());

            int m = ts.size();
            bool flag = false;
            for (int i = 2; i < m; i++)
                if (ts[i] - ts[i - 2] <= 60) {
                    flag = true;
                    break;
                }

            if (flag)
                ans.push_back(person.first);
        }

        sort(ans.begin(), ans.end());

        return ans;
    }
};