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 "22:51" - "23:52" is not considered to be within a one-hour period.

&nbsp;
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").


&nbsp;
Constraints:


	1 &lt;= keyName.length, keyTime.length &lt;= 105
	keyName.length == keyTime.length
	keyTime[i] is in the format "HH:MM".
	[keyName[i], keyTime[i]] is unique.
	1 &lt;= keyName[i].length &lt;= 10
	keyName[i] contains only lowercase English letters.


class Solution:
    # 668 ms, 99.52%. Time: O(NlogN). Space: O(N)
    def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
        
        def is_within_1hr(t1, t2):
            h1, m1 = t1.split(":")
            h2, m2 = t2.split(":")
            if int(h1) + 1 < int(h2): return False
            if h1 == h2: return True
            return m1 >= m2
        
        records = collections.defaultdict(list)
        for name, time in zip(keyName, keyTime):
            records[name].append(time)
        
        rv = []
        for person, record in records.items():
            record.sort()
			# Loop through 2 values at a time and check if they are within 1 hour.
            if any(is_within_1hr(t1, t2) for t1, t2 in zip(record, record[2:])):
                rv.append(person)
        return sorted(rv)
                  
class Solution {
    public List<String> alertNames(String[] keyName, String[] keyTime) {
        Map<String, PriorityQueue<Integer>> map = new HashMap<>();
		// for every entry in keyName and keyTime, add that time to a priorityqueue for that name
        for(int i=0;i<keyName.length;i++){
            PriorityQueue<Integer> pq = map.getOrDefault(keyName[i], new PriorityQueue<Integer>());
			//convert the time to an integer (0- 2359 inclusive) for easy comparisons
            pq.add(Integer.parseInt(keyTime[i].substring(0,2))*100+Integer.parseInt(keyTime[i].substring(3)));
            map.put(keyName[i],pq);
        }
        
		// Generate the "answer" list
        List<String> ans = new ArrayList<>();
        for(String s: map.keySet()){
			// For each name in the map, determine if that name used the keycard within 1 hour
            PriorityQueue<Integer> pq = map.get(s);
            if(active(pq)){
                ans.add(s);
            }
        }
        
		// Sort the names alphabetically
        Collections.sort(ans);
        return ans;
    }
    
	// Greedy function to determine if there were 3 uses within an hour
    private boolean active(PriorityQueue<Integer> pq){
		// If there are two or less entries, the user could not have entered 3 times, return false
        if(pq.size()<3) return false;
		
		// Create rolling data
		// Using PriorityQueues, the lowest number is removed first by default
        int a = pq.poll();
        int b = pq.poll();
        int c = pq.poll();
        
		// Test if two entrances are within 1 hour (100 in integer)
        if(c-a <=100) return true;
        while(pq.size()>0){
            a = b;
            b = c;
            c = pq.poll();
            if(c-a <=100) return true;
        }
		
		// If the full Queue has been checked, return false
        return false;
    }
}
class Solution {
public:
    bool timeDiff(vector<string> timestamp, int index){
        int time1 = ((timestamp[index][0]-'0') * 10 + (timestamp[index][1]-'0')) * 60 + ((timestamp[index][3]-'0') * 10 + (timestamp[index][4]-'0'));
        int time2 = ((timestamp[index+2][0]-'0') * 10 + (timestamp[index+2][1]-'0')) * 60 + ((timestamp[index+2][3]-'0') * 10 + (timestamp[index+2][4]-'0'));
        
        if(abs(time2-time1)<=60) return true;
        return false;
    }
    
    vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
        unordered_map<string, vector<string>> ht;
        
        for(int i=0; i<keyName.size(); i++)
            ht[keyName[i]].push_back(keyTime[i]);
        
        vector<string> result;
        for(auto time : ht){
            sort(time.second.begin(), time.second.end());
            for(int i=0; i+2<time.second.size(); i++)
                if(timeDiff(time.second, i)){
                    result.push_back(time.first);
                    break;
                }
        }
        
        sort(result.begin(), result.end());
        return result;
    }
};

/*
Algorithm Outline
1. store in HT as vector
2. Check for each, 1st & 3rd in range. True if Yes
*/
/**
 * @param {string[]} keyName
 * @param {string[]} keyTime
 * @return {string[]}
 */
var alertNames = function(keyName, keyTime) {
    // so we don't keep duplicates
    const abusers = new Set();
    // map: name->times[] (sorted)
    const times = {};
    for (let i=0; i<keyName.length; i++) {
        const name = keyName[i];
        const time = keyTime[i];
        if (times[name] == null) times[name] = [];
        times[name].push(time);
        
        if (times[name].length > 2) {
            times[name].sort();
            const len = times[name].length;
            // we check all triples for a time difference below 1 hour.
            // as times are sorted, we need to check all i and i+2
            for (let i=0; i<len-2; i++) {
                if (belowHour(times[name][i], times[name][i+2])) {    
                    abusers.add(name);
                }
            }
        }
        
    }
    const ar = Array.from(abusers);
    // sort them lexicographically
    ar.sort();
    return ar;
        
    /*
    same hour: true
    hour diff is above 1: false
    hour diff is 1: m2 must be <= m1
    */
    function belowHour(t1, t2) {
        const [h1, m1] = t1.split(':').map(num => parseInt(num));
        const [h2, m2] = t2.split(':').map(num => parseInt(num));
        if (h1 === h2) return true;
        if (h2-h1 > 1) return false;
        if (m2 <= m1) return true;
    }
};
Alert Using Same Key-Card Three or More Times in a One Hour Period