Skip to content

Latest commit

 

History

History
133 lines (115 loc) · 4.7 KB

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

File metadata and controls

133 lines (115 loc) · 4.7 KB
Raw

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

the second one in Biweekly Contest 36.

Difficulty : Medium

Related Topics : String、Ordered Map

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.

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").

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"]

Constraints:

  • 1 <= keyName.length, keyTime.length <= 10^5
  • keyName.length == keyTime.length
  • keyTime are in the format "HH:MM".
  • [keyName[i], keyTime[i]] is unique.
  • 1 <= keyName[i].length <= 10
  • keyName[i] contains only lowercase English letters.

Solution

  • mine
    • Java
      • Runtime: 86 ms, faster than 66.99%, Memory Usage: 61.3 MB, less than 5.96% of Java online submissions 
        public List<String> alertNames(String[] keyName, String[] keyTime) {
    Map<String, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < keyName.length; i++) {
        List<Integer> list = map.getOrDefault(keyName[i], new ArrayList<>());
        String[] t = keyTime[i].split(":");
        list.add(Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]));
        map.put(keyName[i], list);
    }
    List<String> res = new ArrayList<>();
    for (String key : map.keySet()) {
        if (check(map.get(key))) {
            res.add(key);
        }
    }
    Collections.sort(res);
    return res;
}

boolean check(List<Integer> values) {
    if (values.size() < 3) return false;
    Collections.sort(values);
    LinkedList<Integer> list = new LinkedList<>();
    for (int v : values) {
        while (!list.isEmpty() && Math.abs(v - list.getFirst()) > 60) {
            list.removeFirst();
        }
        list.add(v);
        if (list.size() == 3) return true;
    }
    return false;
}
  • the most votes
  • Runtime: 73 ms, faster than 81.94%, Memory Usage: 65.1 MB, less than 5.96% of Java online submissions 
    public List<String> alertNames(String[] keyName, String[] keyTime) {
    Map<String, TreeSet<Integer>> nameToTime = new HashMap<>();
    for (int i = 0; i < keyName.length; ++i) {
        int time = Integer.parseInt(keyTime[i].substring(0, 2)) * 60 + Integer.parseInt(keyTime[i].substring(3));
        nameToTime.computeIfAbsent(keyName[i], s -> new TreeSet<>()).add(time);
    }
    TreeSet<String> names = new TreeSet<>();
    for (Map.Entry<String, TreeSet<Integer>> e : nameToTime.entrySet()) {
        List<Integer> list = new ArrayList<>(e.getValue());
        for (int i = 2; i < list.size(); ++i) {
            if (list.get(i) - list.get(i - 2) <= 60 ) {
                names.add(e.getKey());
                break;
            }
        }
    }
    return new ArrayList<>(names);
}