Leetcode-1604. Warning people who use the same employee card more than or equal to three times within one hour

link

1604. Warn people who use the same employee card more than three times in an hour

subject

All the employees in Li Kou company use employee cards to open the office door . Every time an employee uses his employee card , The security system records the name and time of use of the employee . If an employee uses the employee card more than or equal to three times in an hour , The system will automatically release a Warning  .

Here's an array of strings  keyName  and  keyTime , among  [keyName[i], keyTime[i]]  Corresponding to a person's name and where he is   One day The time of using the employee card in .

The format of using time is 24 hourly  , Form like  "HH:MM" , For example  "23:51" and  "09:49" .

Please return the name of the employee who received the system warning after de duplication , Press them Dictionary order, ascending order   Sort and return .

Please note that  "10:00" - "11:00"  Within an hour , and  "23:51" - "00:10"  Not considered within an hour , Because the system records the usage in a certain day .

Example

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"]
explain ："daniel" Used in an hour 3 Second employee card （"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"]
explain ："bob" Used in an hour 3 Second employee card （"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"]

Tips

• 1 <= keyName.length, keyTime.length <= 10e5
• keyName.length == keyTime.length
• keyTime The format is  "HH:MM" .
• Guarantee  [keyName[i], keyTime[i]]  The binary pair formed   Different from each other  .
• 1 <= keyName[i].length <= 10
• keyName[i]  Only lowercase letters .

Ideas

Follow the steps directly ：

1. Change all the time from string to concrete int Minutes of type , Convenient comparison , Such as 13:10, Turn it into 13*60+10=790

2. Create a hash table , Store the card swiping time of each employee , Traversal hash table , Deal with each employee's time

3. Sort employees' time , Traversal , If the difference between the third time and the first time ≤60 Words , Explain that the employee swiped the card more than three times an hour , Take out the employee's name and store it in the result array .

4. Because the title requires that the employee names should be sorted in ascending order according to the dictionary and then returned , So finally, you need to do a sorting process .

C++ Code

class Solution {
public:
    vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
        int n=keyName.size();
        vector<string> ans;
        if(n < 3) return ans; 
        unordered_map<string, vector<int>> map; // Store everyone's card swiping time 
        for(int i = 0; i < n; i++) //  Turn the time format into a number of minutes 
        { 
            int H= stoi(keyTime[i].substr(0, 2));
            int M= stoi(keyTime[i].substr(3, 2));
            map[keyName[i]].push_back(60*H+M);
        }
        for(auto [x,y]:map)
        {
            if(y.size()<3) continue;
            sort(y.begin(),y.end());
            for(int i=2;i<y.size();i++)
            {
                if(y[i]-y[i-2]<=60)
                {
                    ans.push_back(x);
                    break;
                }
            }
        }
        sort(ans.begin(),ans.end());
        return ans;
    }
};