Skip to content

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

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
 public:
  vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
    vector<string> ans;
    unordered_map<string, vector<int>> nameToMinutes;

    for (int i = 0; i < keyName.size(); ++i) {
      const int minutes = getMinutes(keyTime[i]);
      nameToMinutes[keyName[i]].push_back(minutes);
    }

    for (auto& [name, minutes] : nameToMinutes)
      if (hasAlert(minutes))
        ans.push_back(name);

    ranges::sort(ans);
    return ans;
  }

 private:
  // Returns true if any worker uses the key-card three or more times in an
  // one-hour period.
  bool hasAlert(vector<int>& minutes) {
    if (minutes.size() > 70)
      return true;
    ranges::sort(minutes);
    for (int i = 2; i < minutes.size(); ++i)
      if (minutes[i - 2] + 60 >= minutes[i])
        return true;
    return false;
  }

  int getMinutes(const string& time) {
    const int h = stoi(time.substr(0, 2));
    const int m = stoi(time.substr(3));
    return 60 * h + m;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
  public List<String> alertNames(String[] keyName, String[] keyTime) {
    List<String> ans = new ArrayList<>();
    HashMap<String, List<Integer>> nameToMinutes = new HashMap<>();

    for (int i = 0; i < keyName.length; i++) {
      final int minutes = getMinutes(keyTime[i]);
      nameToMinutes.putIfAbsent(keyName[i], new ArrayList<>());
      nameToMinutes.get(keyName[i]).add(minutes);
    }

    for (Map.Entry<String, List<Integer>> entry : nameToMinutes.entrySet()) {
      final String name = entry.getKey();
      List<Integer> minutes = entry.getValue();
      if (hasAlert(minutes))
        ans.add(name);
    }

    Collections.sort(ans);
    return ans;
  }

  private boolean hasAlert(List<Integer> minutes) {
    if (minutes.size() > 70)
      return true;
    Collections.sort(minutes);
    for (int i = 2; i < minutes.size(); i++)
      if (minutes.get(i - 2) + 60 >= minutes.get(i))
        return true;
    return false;
  }

  private int getMinutes(String time) {
    final int h = Integer.parseInt(time.substring(0, 2));
    final int m = Integer.parseInt(time.substring(3));
    return 60 * h + m;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def alertNames(self, keyName: list[str], keyTime: list[str]) -> list[str]:
    nameToMinutes = collections.defaultdict(list)

    for name, time in zip(keyName, keyTime):
      minutes = self._getMinutes(time)
      nameToMinutes[name].append(minutes)

    return sorted([name for name, minutes in nameToMinutes.items()
                   if self._hasAlert(minutes)])

  def _hasAlert(self, minutes: list[int]) -> bool:
    if len(minutes) > 70:
      return True
    minutes.sort()
    for i in range(2, len(minutes)):
      if minutes[i - 2] + 60 >= minutes[i]:
        return True
    return False

  def _getMinutes(self, time: str) -> int:
    h, m = map(int, time.split(':'))
    return 60 * h + m