Leetcode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker’s name and the time when it was used. The system emits an alert if any worker uses the key-card three or more times in a one-hour period.
You are given a list of strings keyName and keyTime where [keyName[i], keyTime[i]] corresponds to a person’s name and the time when their key-card was used in a single day.
Access times are given in the 24-hour time format “HH:MM”, such as "23:51" and "09:49".
Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.
Notice that "10:00" – "11:00" is considered to be within a one-hour period, while "23:51" – "00:10" is not considered to be within a one-hour period.
Example 1:
Input: keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
Output: ["daniel"]
Explanation: "daniel" used the keycard 3 times in a one-hour period ("10:00","10:40", "11:00").
Example 2:
Input: keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
Output: ["bob"]
Explanation: "bob" used the keycard 3 times in a one-hour period ("21:00","21:20", "21:30").
Example 3:
Input: keyName = ["john","john","john"], keyTime = ["23:58","23:59","00:01"] Output: []
Example 4:
Input: keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"], keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"] Output: ["clare","leslie"]
Constraints:
1 <= keyName.length, keyTime.length <= 105keyName.length == keyTime.lengthkeyTimeare in the format “HH:MM”.[keyName[i], keyTime[i]]is unique.1 <= keyName[i].length <= 10keyName[i] contains only lowercase English letters.
Solution: Hashtable + sorting
Time complexity: O(nlogn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution { public: vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) { unordered_map<string, vector<int>> t; // {name -> time} for (size_t i = 0; i < keyName.size(); ++i) { const int h = stoi(keyTime[i].substr(0, 2)); const int m = stoi(keyTime[i].substr(3)); t[keyName[i]].push_back(h * 60 + m); } vector<string> ans; for (auto& [name, times] : t) { sort(begin(times), end(times)); for (size_t i = 2; i < times.size(); ++i) if (times[i] - times[i - 2] <= 60) { ans.push_back(name); break; } } sort(begin(ans), end(ans)); return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment