Problem Description
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". Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.
Key Insights
- We need to track the number of times each worker uses their key-card.
- We must check if any of these usages occur within a one-hour window.
- Sorting the key times for each worker will allow us to efficiently check for the one-hour condition.
- Only unique worker names who triggered the alert should be returned.
Space and Time Complexity
Time Complexity: O(n log n) - where n is the number of key usages (due to sorting). Space Complexity: O(n) - to store the list of key usages and alerts.
Solution
To solve this problem, we can use a hash map (dictionary) to group key usages by worker names. For each worker, we will store their corresponding key usage times in a list. After collecting all usages, we will sort these times for each worker. By iterating through the sorted times, we can check for any three usages that fall within a one-hour period. If found, we will add the worker's name to the alert list. Finally, we will return the sorted list of unique worker names.