{"id":7442,"date":"2020-10-03T16:03:13","date_gmt":"2020-10-03T23:03:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7442"},"modified":"2020-10-03T16:03:53","modified_gmt":"2020-10-03T23:03:53","slug":"leetcode-1604-alert-using-same-key-card-three-or-more-times-in-a-one-hour-period","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1604-alert-using-same-key-card-three-or-more-times-in-a-one-hour-period\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period"},"content":{"rendered":"\n

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<\/strong> if any worker uses the key-card three or more times<\/strong> in a one-hour period.<\/p>\n\n\n\n

You are given a list of strings keyName<\/code> and keyTime<\/code> where [keyName[i], keyTime[i]]<\/code> corresponds to a person’s name and the time when their key-card was used in a<\/strong> single day<\/strong>.<\/p>\n\n\n\n

Access times are given in the 24-hour time format “HH:MM”<\/strong>, such as \"23:51\"<\/code> and \"09:49\"<\/code>.<\/p>\n\n\n\n

Return a list of unique worker names who received an alert for frequent keycard use<\/em>. Sort the names in ascending order alphabetically<\/strong>.<\/p>\n\n\n\n

Notice that \"10:00\"<\/code> – \"11:00\"<\/code> is considered to be within a one-hour period, while \"23:51\"<\/code> – \"00:10\"<\/code> is not considered to be within a one-hour period.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> keyName = [\"daniel\",\"daniel\",\"daniel\",\"luis\",\"luis\",\"luis\",\"luis\"], keyTime = [\"10:00\",\"10:40\",\"11:00\",\"09:00\",\"11:00\",\"13:00\",\"15:00\"]\nOutput:<\/strong> [\"daniel\"]\nExplanation:<\/strong> \"daniel\" used the keycard 3 times in a one-hour period (\"10:00\",\"10:40\", \"11:00\").\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> keyName = [\"alice\",\"alice\",\"alice\",\"bob\",\"bob\",\"bob\",\"bob\"], keyTime = [\"12:01\",\"12:00\",\"18:00\",\"21:00\",\"21:20\",\"21:30\",\"23:00\"]\nOutput:<\/strong> [\"bob\"]\nExplanation:<\/strong> \"bob\" used the keycard 3 times in a one-hour period (\"21:00\",\"21:20\", \"21:30\").\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> keyName = [\"john\",\"john\",\"john\"], keyTime = [\"23:58\",\"23:59\",\"00:01\"]\nOutput:<\/strong> []\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> keyName = [\"leslie\",\"leslie\",\"leslie\",\"clare\",\"clare\",\"clare\",\"clare\"], keyTime = [\"13:00\",\"13:20\",\"14:00\",\"18:00\",\"18:51\",\"19:30\",\"19:49\"]\nOutput:<\/strong> [\"clare\",\"leslie\"]\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= keyName.length, keyTime.length <= 105<\/sup><\/code><\/li>
  • keyName.length == keyTime.length<\/code><\/li>
  • keyTime<\/code> are in the format “HH:MM”<\/strong>.<\/li>
  • [keyName[i], keyTime[i]]<\/code> is unique<\/strong>.<\/li>
  • 1 <= keyName[i].length <= 10<\/code><\/li>
  • keyName[i] contains only lowercase English letters.<\/code><\/li><\/ul>\n\n\n\n
    Solution: Hashtable + sorting<\/strong><\/h2>\n\n\n\n
    Time complexity: O(nlogn)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  vector alertNames(vector& keyName, vector& keyTime) {\n    unordered_map> t; \/\/ {name -> time}\n    for (size_t i = 0; i < keyName.size(); ++i) {\n      const int h = stoi(keyTime[i].substr(0, 2));\n      const int m = stoi(keyTime[i].substr(3));\n      t[keyName[i]].push_back(h * 60 + m);\n    }\n    vector ans;\n    for (auto& [name, times] : t) {\n      sort(begin(times), end(times));\n      for (size_t i = 2; i < times.size(); ++i)\n        if (times[i] - times[i - 2] <= 60) {\n          ans.push_back(name);\n          break;\n        }   \n    }\n    sort(begin(ans), end(ans));\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[82,177,15],"class_list":["post-7442","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-medium","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7442","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7442"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7442\/revisions"}],"predecessor-version":[{"id":7444,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7442\/revisions\/7444"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7442"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7442"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7442"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}