Alert Using Same Key-Card Three or More Times in a One Hour Period

Problem Description

Given two lists keyName and keyTime where each pair [keyName[i], keyTime[i]] represents a worker and the time (in "HH:MM" 24-hour format) they used their key-card during a single day, determine which workers received an alert. A worker receives an alert if they used their key-card three or more times within any one-hour period. The output should be a sorted list (alphabetically) of unique names that met this condition.

Key Insights

• Convert time strings "HH:MM" into a total minute count to simplify comparing time differences.
• Group key usage times by worker name.
• Sort the times for each worker to enable sequential checking of three consecutive uses.
• Use a sliding window (or simply check every triplet) to see if the difference between the earliest and the third keycard usage is within 60 minutes.
• Ensure a one-hour period means that the time difference equal to 60 minutes (for example, "10:00" to "11:00") is valid.

Space and Time Complexity

Time Complexity: O(n log n) where n is the number of key card uses because each worker's times are sorted. Space Complexity: O(n) to store the mapping from worker names to their converted times.

Solution

1. Create a dictionary to map each worker's name to a list of their usage times converted to minutes.
2. For each keyTime string, convert it to total minutes (hours * 60 + minutes) and populate the dictionary.
3. For each worker, sort their list of times.
4. Traverse through the sorted times using a sliding window of size 3. For each window, check if the difference between the first and third entries is less than or equal to 60 minutes. If it is, record the worker and stop further checks for that worker.
5. Sort the resulting list of employees who triggered an alert alphabetically and return it.

Code Solutions