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 <= 105
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.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Sorting

Data structures

Starter code: class Solution:
    def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
        

Solutions:
class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def should_alert(t):
			if len(t) < 3:
				return False
			for i in range(len(t) - 2):
				if t[i + 2] <= t[i] + 100:
					return True
			return False
		time = collections.defaultdict(list)
		alert = []
		for (name, t) in zip(keyName, keyTime):
			ti = int(t[:2] + t[3:])
			time[name].append(ti)
		ret = []
		for name in time:
			time[name].sort()
			if should_alert(time[name]):
				ret.append(name)
		ret.sort()
		return ret


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		checker = {}
		l = len(keyName)
		for i in range(l):
			if keyName[i] not in checker:
				checker[keyName[i]] = [keyTime[i]]
			else:
				checker[keyName[i]].append(keyTime[i])
		ans = []
		for (a, b) in checker.items():
			l = len(b)
			if l > 2:
				b.sort()
				for i in range(l - 2):
					t = b[i].split(':')
					t = str(int(t[0]) + 1) + ':' + t[1]
					if len(t) == 4:
						t = '0' + t
					if t >= b[i + 2]:
						ans.append(a)
						break
		ans.sort()
		return ans


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def convert_to_minutes(time):
			hhmm = time.split(':')
			(hh, mm) = (int(hhmm[0]), int(hhmm[1]))
			return 60 * hh + mm
		mod = 24 * 60
		res = set()
		minutes = [convert_to_minutes(hhmm) for hhmm in keyTime]
		d = collections.defaultdict(list)
		for i in range(len(minutes)):
			worker = keyName[i]
			time = minutes[i]
			d[worker].append(time)
		for worker in d:
			d[worker].sort()
			for i in range(2, len(d[worker])):
				if d[worker][i] - d[worker][i - 2] <= 60:
					res.add(worker)
					break
		return sorted(list(res))


from sortedcontainers import SortedList

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		hm = defaultdict(SortedList)
		res = set()
		for (name, time) in zip(keyName, keyTime):
			int_time = self.get_time_as_int(time)
			hm[name].add(int_time)
		for name in hm:
			if self.check(hm[name]):
				res.add(name)
		return sorted(res)

	def check(self, arr):
		left = 0
		for right in range(len(arr)):
			if right - left + 1 == 3:
				if arr[right] - arr[left] <= 100:
					return True
				left += 1
		return False

	def get_time_as_int(self, time):
		t1 = time[:2]
		t2 = time[3:]
		int_time = int(t1 + t2)
		return int_time


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		dictTime = collections.defaultdict(list)
		setName = set()
		for (x, y) in zip(keyName, keyTime):
			dictTime[x].append(y)
			setName.add(x)
		listName = list(setName)
		listName.sort()
		for key in dictTime:
			dictTime[key].sort()
		print(dictTime)
		out = []
		for name in listName:
			listT = dictTime[name]
			if len(listT) >= 3:
				start = 0
				end = 2
				condit = False
				while end < len(listT):
					if int(listT[start][:2]) == int(listT[end][:2]):
						condit = True
						break
					if int(listT[start][:2]) + 1 == int(listT[end][:2]) and int(listT[start][3:]) >= int(listT[end][3:]):
						condit = True
						break
					start += 1
					end = start + 2
				if condit:
					out.append(name)
		return out


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		records = collections.defaultdict(list)
		for (name, time) in zip(keyName, keyTime):
			(minutes, seconds) = (int(time[:2]), int(time[-2:]))
			records[name].append(60 * minutes + seconds)
		res = []
		for name in records:
			q = collections.deque()
			found = False
			for time in sorted(records[name]):
				while q and abs(time - q[0]) > 60:
					q.popleft()
				q.append(time)
				if len(q) >= 3:
					found = True
					break
			if found:
				res.append(name)
		return sorted(res)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		cands = [(n, int(t[:2]) * 60 + int(t[-2:])) for (n, t) in zip(keyName, keyTime)]
		cands.sort()
		rec = defaultdict(list)
		out = []
		for (n, t) in cands:
			if n in out:
				continue
			if n not in rec:
				rec[n].append(t)
			elif 0 <= abs(t - rec[n][0]) <= 60:
				rec[n].append(t)
			else:
				while rec[n] and abs(t - rec[n][0]) > 60:
					rec[n].pop(0)
				rec[n].append(t)
				rec[n].sort()
			if len(rec[n]) == 3:
				out.append(n)
		return sorted(out)


import datetime as dt
from collections import defaultdict

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		access = defaultdict(list)
		res = set()
		NameTime = []
		for i in range(len(keyName)):
			name = keyName[i]
			(h, m) = map(int, keyTime[i].split(':'))
			d = dt.datetime(2020, 10, 6, h, m)
			NameTime.append([d, name])
		NameTime.sort()
		period = dt.timedelta(hours=1)
		for (d, name) in NameTime:
			if name not in res:
				while access[name] and access[name][0] + period < d:
					access[name].pop(0)
				access[name].append(d)
				if len(access[name]) >= 3:
					res.add(name)
		return sorted(list(res))


class Solution:

	def alertNames(self, names: List[str], times: List[str]) -> List[str]:
		m = {}
		N = len(names)
		alerts = set()
		minutes = lambda time: int(time.split(':')[0]) * 60 + int(time.split(':')[1])
		for (name, time) in zip(names, times):
			if name not in m:
				m[name] = deque()
			m[name].append(minutes(time))
		for (name, times) in m.items():
			q = deque()
			for time in sorted(times):
				while len(q) and q[0] + 60 < time:
					q.popleft()
				q.append(time)
				if 3 <= len(q):
					alerts.add(name)
					break
		return sorted(alerts)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		records = defaultdict(list)
		alerts = set()
		for i in range(len(keyName)):
			records[keyName[i]].append(keyTime[i])
		for (k, v) in list(records.items()):
			if len(v) < 3:
				continue
			else:
				r = sorted(v, key=lambda word: (int(word[0:2]), int(word[3:5])))
				for j in range(0, len(r) - 2):
					start = r[j]
					end = r[j + 2]
					time1 = start.split(':')
					time2 = end.split(':')
					md = int(time2[1]) - int(time1[1])
					hd = int(time2[0]) - int(time1[0])
					f = 0
					if md < 0:
						md += 60
						f = -1
					td = md + (hd + f) * 60
					if 0 < td <= 60:
						if k not in alerts:
							alerts.add(k)
							break
		return sorted(list(alerts))


def compareTimesStr(beginStr, endStr):
	return compareTimes(int(beginStr[:2]), int(beginStr[-2:]), int(endStr[:2]), int(endStr[-2:]))

def compareTimes(beginHr: int, beginMin: int, endHr: int, endMin: int):
	if endHr < beginHr:
		return False
	if beginHr == endHr:
		return True
	elif endHr - beginHr > 1:
		return False
	else:
		return endMin - beginMin <= 0

def hasAlert(times: List[str]) -> bool:
	if len(times) < 3:
		return False
	times.sort()
	i = 0
	while i < len(times) - 2:
		if compareTimesStr(times[i], times[i + 2]):
			return True
		i += 1
	return False

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		ans = []
		if len(keyName) < 3:
			return ans
		zippedPairs = list(zip(keyName, keyTime))
		keyTime = [x for (_, x) in sorted(zippedPairs)]
		print(keyTime)
		keyName.sort()
		start = 0
		for i in range(len(keyName)):
			if keyName[i] == keyName[start] and i < len(keyName) - 1:
				pass
			elif i < len(keyName) - 1:
				if hasAlert(keyTime[start:i]):
					ans.append(keyName[start])
				start = i
			elif hasAlert(keyTime[start:i + 1]):
				ans.append(keyName[start])
		return sorted(ans)


from collections import defaultdict

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		d = defaultdict(list)
		ans = []
		for i in range(len(keyName)):
			temp = keyTime[i].strip().split(':')
			d[keyName[i]].append(int(temp[0] + temp[1]))
			names = list(d.keys())
		for i in names:
			count = 0
			times = d[i]
			times.sort()
			for j in range(len(times) - 2):
				curr = times[j]
				nex = times[j + 2]
				if abs(curr - nex) <= 100:
					if i not in ans:
						ans.append(i)
		return sorted(ans)


def within_hour(large, small):
	if abs(large[0] - small[0]) >= 2:
		return False
	if large[0] - small[0] == 1 and small[1] < large[1]:
		print((large, small))
		return False
	return True

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		sorted_list = sorted(zip(keyTime, keyName))
		alerted = []
		people = {}
		for (time_str, name) in sorted_list:
			if name not in alerted:
				time = [int(time_str[:2]), int(time_str[-2:])]
				if name in list(people.keys()):
					if len(people[name]) == 2:
						if within_hour(time, people[name][1]):
							people[name].append(time)
							if not within_hour(time, people[name][0]):
								del people[name][0]
							else:
								alerted.append(name)
						else:
							people[name] = [time]
					elif not within_hour(time, people[name][0]):
						people[name] = [time]
					else:
						people[name].append(time)
				else:
					people[name] = [time]
		return sorted(alerted)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		n = len(keyName)
		alert = defaultdict(dict)
		ans = []
		zipper = list(zip(keyName, keyTime))
		zipper = list(zipper)
		zipper.sort(key=lambda x: (x[0], x[1]))
		for i in range(n - 2):
			(name, time) = zipper[i]
			if name in ans:
				continue
			(next_name, next_time) = zipper[i + 2]
			if next_name != name:
				continue
			time = int(time[:2] + time[3:])
			next_time = int(next_time[:2] + next_time[3:])
			if next_time - time <= 100:
				ans.append(name)
		return ans


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		dic = {}
		res = set()
		for i in range(len(keyName)):
			name = keyName[i]
			time = keyTime[i]
			if name not in dic:
				dic[name] = []
			time = list(map(int, time.split(':')))
			time = time[0] + time[1] / 60
			dic[name].append(time)
		for name in dic:
			t = sorted(dic[name])
			if len(t) >= 3:
				for j in range(len(t) - 2):
					if t[j + 2] - t[j] <= 1.0001:
						res.add(name)
		return sorted(list(res))


class Solution:

	def alertNames(self, names: List[str], times: List[str]) -> List[str]:
		dic = {}
		n = len(names)
		alert = set()
		arr = [tup for tup in zip(names, times)]
		arr.sort(key=lambda ele: ele[1])
		for i in range(n):
			(name, time) = (arr[i][0], arr[i][1])
			tup = time.split(':')
			(hour, minu) = (int(tup[0]), int(tup[1]))
			int_time = hour * 60 + minu
			dic[name] = dic.get(name, []) + [int_time]
			curlen = len(dic[name])
			if curlen >= 3 and int_time - dic[name][curlen - 3] <= 60:
				alert.add(name)
		return sorted(list(alert))


from collections import deque

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		usermap = {}
		ansmap = {}

		def strtomin(foo):
			return int(foo[0:2]) * 60 + int(foo[3:])

		def analyze(foo):
			d = deque()
			for i in foo:
				d.append(i)
				while d[0] < i - 60:
					d.popleft()
				if len(d) >= 3:
					return True
			return False
		for i in range(len(keyName)):
			name = keyName[i]
			time = strtomin(keyTime[i])
			if name not in usermap:
				usermap[name] = []
			usermap[name].append(time)
		for i in usermap:
			usermap[i].sort()
			if analyze(usermap[i]):
				ansmap[i] = True
		return sorted(ansmap.keys())


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		Info = [[keyTime[i], keyName[i]] for i in range(len(keyName))]
		Info.sort()
		keyTime = [x[0] for x in Info]
		keyName = [x[1] for x in Info]
		cnt = collections.defaultdict(lambda : collections.deque())

		def diff(prev, curr):
			val = (int(curr[:2]) - int(prev[:2])) * 60 + int(curr[3:]) - int(prev[3:])
			return val > 60 or val < 0
		res = set()
		for i in range(len(keyName)):
			curr = keyTime[i]
			while cnt[keyName[i]] and diff(cnt[keyName[i]][0], curr):
				cnt[keyName[i]].popleft()
			if len(cnt[keyName[i]]) >= 2:
				res.add(keyName[i])
			cnt[keyName[i]].append(curr)
		return sorted(res)


from sortedcontainers import SortedList

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		alerted_workers = set()
		worker_enter = {}
		for (name, time) in zip(keyName, keyTime):
			if name in alerted_workers:
				continue
			time = int(time[:2]) * 60 + int(time[-2:])
			if not name in worker_enter:
				worker_enter[name] = SortedList()
			if len(worker_enter[name]) >= 2:
				index = worker_enter[name].bisect(time)
				if index - 2 >= 0 and time - worker_enter[name][index - 2] <= 60 or (index - 1 >= 0 and index < len(worker_enter[name]) and (worker_enter[name][index] - worker_enter[name][index - 1] <= 60)) or (index + 1 < len(worker_enter[name]) and worker_enter[name][index + 1] - time <= 60):
					alerted_workers.add(name)
			worker_enter[name].add(time)
		return list(sorted(alerted_workers))


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		dic = collections.defaultdict(list)
		ans = set()
		for (name, time) in sorted(zip(keyName, keyTime), key=lambda x: x[1]):
			if name not in ans:
				(h, m) = map(int, time.split(':'))
				t = h * 60 + m
				if len(dic[name]) >= 2 and dic[name][-2] >= t - 60:
					ans.add(name)
					del dic[name]
				else:
					dic[name].append(t)
					dic[name] = dic[name][-2:]
		return sorted(ans)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def get_time(time):
			return int(time[:2]) * 60 + int(time[3:])
		map = {}
		for (name, time) in zip(keyName, keyTime):
			if name not in map:
				map[name] = []
			map[name].append(get_time(time))
		ans = []
		for name in sorted(map.keys()):
			times = sorted(map[name])
			for i in range(len(times) - 2):
				if times[i + 2] - times[i] <= 60:
					ans.append(name)
					break
		return ans


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		from collections import defaultdict, deque
		maps = defaultdict(deque)
		res = set()
		for (name, time) in sorted(zip(keyName, keyTime)):
			h = int(time[:2])
			m = int(time[3:])
			t = h * 60 + m
			queue = maps[name]
			while queue and queue[0][0] * 60 + queue[0][1] < t - 60:
				queue.popleft()
			queue.append([h, m])
			if len(queue) >= 3:
				res.add(name)
		return sorted(res)


from collections import deque, defaultdict

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def time(s):
			(hr, mn) = map(int, s.split(':'))
			return hr * 60 + mn
		ans = set()
		d = defaultdict(deque)
		l = list(zip(keyName, map(time, keyTime)))
		l.sort(key=lambda x: x[1])
		for (k, t) in l:
			d[k].append(t)
			if len(d[k]) == 3 and t - d[k].popleft() <= 60:
				ans.add(k)
		return sorted(ans)


import math

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		dic = {}
		for (i, name) in enumerate(keyName):
			t = keyTime[i]
			if name in dic:
				dic[name].append(int(t[0:2] + t[3:]))
			else:
				dic.setdefault(name, [int(t[0:2] + t[3:])])
		alert = []

		def ihan(name):
			timeList = dic[name]
			timeList.sort()
			print(dic[name])
			for t in range(len(timeList) - 2):
				print(math.floor(timeList[t] / 100) * 100)
				if timeList[t + 2] > timeList[t] and timeList[t + 2] - timeList[t] <= 100:
					return True
			return False
		for name in dic:
			if len(dic[name]) > 2 and ihan(name):
				alert.append(name)
			alert.sort()
		return alert


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def calcmin(t: str) -> int:
			return int(t[:2]) * 60 + int(t[3:])
		(key, res) = ({}, [])
		for (i, v) in enumerate(keyName):
			if not v in key:
				key[v] = []
			key[v] += [keyTime[i]]
		for k in key:
			key[k].sort()
			for i in range(2, len(key[k])):
				if calcmin(key[k][i]) - calcmin(key[k][i - 2]) <= 60:
					res += [k]
					break
		return sorted(res)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		tm = list(map(lambda x: int(x.split(':')[0]) * 60 + int(x.split(':')[1]), keyTime))
		ans = set()
		tmp = []
		for (name, tm) in zip(keyName, tm):
			tmp.append((tm, name))
		tmp.sort()
		d = defaultdict(deque)
		for (time, name) in tmp:
			while d[name] and abs(time - d[name][0]) > 60:
				d[name].popleft()
			d[name].append(time)
			if len(d[name]) >= 3:
				ans.add(name)
		return sorted(ans)


class Solution:

	def within_hour(self, t1, t2):
		(hh1, ss1) = list(map(int, t1.split(':')))
		(hh2, ss2) = list(map(int, t2.split(':')))
		hdiff = hh2 - hh1
		if hdiff > 1 or hdiff < 0:
			return False
		sdiff = ss2 - ss1
		return hdiff * 60 + sdiff <= 60

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		d = {}
		result = set()
		for (kn, kt) in zip(keyName, keyTime):
			if kn in d:
				d[kn].append(kt)
			else:
				d[kn] = [kt]
		result = []
		for (k, v) in list(d.items()):
			v.sort(key=lambda x: tuple(map(int, x.split(':'))))
			for i in range(len(v) - 2):
				if self.within_hour(v[i], v[i + 2]):
					result.append(k)
					break
		return sorted(result)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		arr = sorted(zip(keyName, keyTime), key=lambda x: self.convert(x[1]))
		times = defaultdict(list)
		ans = set()
		for (name, time) in arr:
			time = self.convert(time)
			if name not in ans:
				if len(times[name]) >= 2 and abs(time - min(times[name])) <= 60:
					ans.add(name)
					continue
				times[name].append(time)
				times[name].sort()
				while times[name][-1] - times[name][0] > 60:
					times[name].pop(0)
		return sorted(ans)

	def convert(self, time):
		hours = 60 * int(time[0:2])
		minutes = int(time[3:5])
		return hours + minutes


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		out = []
		freq = {}
		alerts = {}
		for i in range(len(keyName)):
			seconds = int(keyTime[i][:2]) * 60 + int(keyTime[i][-2:])
			if keyName[i] in alerts:
				alerts[keyName[i]].append(seconds)
			else:
				alerts[keyName[i]] = [seconds]
				freq[keyName[i]] = 0
		print(alerts)
		for (name, time) in list(alerts.items()):
			for i in range(len(time) - 2):
				time = sorted(time)
				if time[i + 1] - time[i] <= 60 and time[i + 2] - time[i] <= 60:
					freq[name] += 1
		print(freq)
		for (name, _) in list(freq.items()):
			if freq[name] >= 1:
				out.append(name)
		return sorted(out)


from collections import defaultdict

class Solution:

	def alertNames(self, name: List[str], time: List[str]) -> List[str]:
		li = [[int(t[0:2]) * 100 + int(t[3:]), n] for (t, n) in zip(time, name)]
		li = sorted(li)
		d = defaultdict(int)
		dc = defaultdict(int)
		n = len(name)
		(i, j) = (0, 0)
		ans = 0
		s = set()
		while i <= j and j < n:
			if li[j][0] - li[i][0] == 0:
				d[li[j][1]] = 1
				j += 1
			elif li[j][0] - li[i][0] <= 100:
				d[li[j][1]] += 1
				if d[li[j][1]] >= 3:
					s.add(li[j][1])
				j += 1
			else:
				d[li[i][1]] -= 1
				i += 1
		return sorted(list(s))


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def to_minutes(s):
			(h, m) = list(map(int, s.split(':')))
			return h * 60 + m
		alerts = set()
		m = defaultdict(list)
		for (time, name) in sorted(((to_minutes(time), name) for (time, name) in zip(keyTime, keyName))):
			times = m[name]
			times.append(time)
			if len(times) >= 3 and times[-3] + 60 >= times[-1]:
				alerts.add(name)
		return sorted(alerts)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		used = {}
		res = set()

		def greaterThanHour(t1, t2):
			t1 = t1.split(':')
			t2 = t2.split(':')
			(h1, h2) = (int(t1[0]), int(t2[0]))
			(m1, m2) = (int(t1[1]), int(t2[1]))
			return (h2 - h1) * 60 + (m2 - m1) > 60
		for (n, t) in zip(keyName, keyTime):
			if n not in used:
				used[n] = []
			used[n].append(t)
		for k in used:
			used[k] = sorted(used[k])
			p1 = p2 = 0
			while p2 < len(used[k]):
				if greaterThanHour(used[k][p1], used[k][p2]):
					p1 += 1
				if p2 - p1 == 2:
					res.add(k)
					break
				p2 += 1
		return sorted(list(res))


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def to_ts(t: str):
			(hour, minute) = t.split(':')
			return 60 * int(hour) + int(minute)

		def in_a_hour(t1, t2):
			return abs(to_ts(t1) - to_ts(t2)) <= 60
		from datetime import datetime
		mapping = {name: [] for name in keyName}
		for i in range(len(keyName)):
			mapping[keyName[i]].append(keyTime[i])
		for val in list(mapping.values()):
			val.sort(key=to_ts)
		print(mapping)

		def more_than_3_in_a_hour(arr):
			l = r = 0
			while r < len(arr):
				if in_a_hour(arr[l], arr[r]):
					if r - l >= 2:
						return True
					r += 1
				else:
					l += 1
		return sorted([name for (name, times) in list(mapping.items()) if more_than_3_in_a_hour(times)])


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		alerts = set()

		def translate(time):
			(hours, minutes) = time.split(':')
			return 60 * int(hours) + int(minutes)
		sorted_times = sorted(enumerate(map(translate, keyTime)), key=lambda p: p[1])
		counts = collections.defaultdict(int)
		q = collections.deque()
		for (i, time) in sorted_times:
			while len(q) and q[0][0] + 60 < time:
				(_, p) = q.popleft()
				counts[p] -= 1
			p = keyName[i]
			counts[p] += 1
			q.append((time, p))
			if counts[p] >= 3:
				alerts.add(p)
		return sorted(alerts)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		d = defaultdict(list)
		if not keyName:
			return []
		n = len(keyName)
		for i in range(n):
			d[keyName[i]].append(keyTime[i])
		ans = []

		def delta(t1, t2):
			t1 = list(map(int, t1.split(':')))
			t2 = list(map(int, t2.split(':')))
			(h1, m1) = t1
			(h2, m2) = t2
			if h2 - h1 > 1 or (h2 - h1 == 1 and m2 > m1):
				return True
			return False
		for name in d:
			times = d[name]
			times.sort()
			cur = [times[0]]
			t = 1
			for i in range(1, len(times)):
				t = times[i]
				cur.append(t)
				while cur and delta(cur[0], t):
					cur.pop(0)
				if len(cur) == 3:
					ans.append(name)
					break
		return sorted(ans)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def getmins(time):
			(h, m) = time.split(':')
			return int(h) * 60 + int(m)

		def timediff(time1, time2):
			return getmins(time1) - getmins(time2)
		d = defaultdict(list)
		for (name, time) in zip(keyName, keyTime):
			d[name].append(time)
		res = []
		for key in d:
			vals = d[key]
			slow = 0
			for fast in range(len(vals)):
				vals.sort()
				while timediff(vals[fast], vals[slow]) > 60:
					slow += 1
				if fast - slow >= 2:
					res.append(key)
					break
		res.sort()
		return res


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		name_to_time = collections.defaultdict(list)
		for (name, hour_minute) in zip(keyName, keyTime):
			(hour, minute) = map(int, hour_minute.split(':'))
			time = hour * 60 + minute
			name_to_time[name].append(time)
		names = []
		for (name, time_list) in name_to_time.items():
			time_list.sort()
			for (i, time) in enumerate(time_list):
				if i >= 2 and time - time_list[i - 2] <= 60:
					names.append(name)
					break
		return sorted(names)


class Solution:

	def alertNames(self, l1: List[str], l2: List[str]) -> List[str]:
		d = {}
		for i in l1:
			d[i] = [-float('inf')]
		ans = set()
		l = [[l1[i], l2[i]] for i in range(len(l1))]
		l.sort(key=lambda x: x[1])
		for i in range(len(l1)):
			l1[i] = l[i][0]
			l2[i] = l[i][1]
		for i in range(len(l1)):
			curr = l2[i]
			curr = curr.split(':')
			curr = int(''.join(curr))
			d[l1[i]].append(curr)
		ans = []
		for i in d:
			for j in range(2, len(d[i])):
				if d[i][j] - d[i][j - 2] <= 100:
					ans.append(i)
					break
		return sorted(ans)


class Solution:
	from collections import defaultdict, deque

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		data = defaultdict(list)
		for (name, t) in zip(keyName, keyTime):
			data[name].append(t)

		def compare(t1, t2):
			t1 = t1.split(':')
			t2 = t2.split(':')
			if t1[0] == t2[0] and t1[1] < t2[1]:
				return True
			if int(t2[0]) - int(t1[0]) == 1 and t1[1] >= t2[1]:
				return True
			return False
		r = []
		for (name, times) in list(data.items()):
			times.sort()
			q = deque()
			for t in times:
				if not q:
					q.append(t)
				else:
					while q and (not compare(q[0], t)):
						q.popleft()
					q.append(t)
					if len(q) >= 3:
						r.append(name)
						break
		return sorted(r)


class Solution:

	def alertNames(self, name: List[str], time: List[str]) -> List[str]:
		d = collections.defaultdict(list)
		for i in range(len(name)):
			c = int(time[i][:2]) * 60 + int(time[i][3:])
			d[name[i]].append(c)
		for i in d:
			d[i].sort()
		ans = []
		for i in d:
			for j in range(len(d[i]) - 2):
				if d[i][j + 2] - d[i][j] <= 60:
					ans.append(i)
					break
		ans.sort()
		return ans


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		temp = []
		for (name, time) in zip(keyName, keyTime):
			temp.append([name, time])
		temp.sort(key=lambda x: (x[0], x[1]))
		ans = []

		def inhour(t1, t3):

			def hrmn(t1):
				(hr, mn) = t1.split(':')
				return int(hr) * 60 + int(mn)
			(it1, it3) = (hrmn(t1), hrmn(t3))
			return it3 - it1 <= 60
		for i in range(2, len(temp)):
			(name1, time1) = temp[i - 2]
			(name3, time3) = temp[i]
			if name1 == name3:
				if inhour(time1, time3) and (len(ans) == 0 or ans[-1] != name1):
					ans.append(name1)
		return ans


def diff(time2, time1):
	t1 = int(time1[:2]) * 60 + int(time1[3:])
	t2 = int(time2[:2]) * 60 + int(time2[3:])
	return t2 - t1

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		l = []
		for (name, time) in zip(keyName, keyTime):
			l.append((name, time))
		l = sorted(l, key=lambda x: x[1])
		keyName = [i[0] for i in l]
		keyTime = [i[1] for i in l]
		result = set()
		index = 0
		hash_map = {}
		i = 0
		while i < len(keyName):
			name = keyName[i]
			time = keyTime[i]
			dif = diff(time, keyTime[index])
			if dif > 60 or dif < 0:
				if dif < 0:
					index = i
					hash_map.clear()
					hash_map[name] = 1
					i += 1
					continue
				elif dif > 60:
					hash_map[keyName[index]] -= 1
					index += 1
					continue
			if hash_map.get(name, -1) == -1:
				hash_map[name] = 1
			else:
				hash_map[name] += 1
			if hash_map[name] >= 3:
				result.add(name)
			i += 1
		result = sorted(list(result))
		return result


from functools import cmp_to_key

def cmp(a, b):
	if a[1] > b[1]:
		return 1
	return -1

def secs(time):
	(hr, mins) = time.split(':')
	s = int(hr) * 3600 + int(mins) * 60
	return s

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		N = len(keyName)
		l = []
		for i in range(N):
			l.append([keyName[i], keyTime[i]])
		l.sort(key=cmp_to_key(cmp))
		d = {}
		s = set()
		for (name, time) in l:
			if name in s:
				continue
			if name not in d:
				d[name] = [secs(time)]
			else:
				i = 0
				curr_time = secs(time)
				while i < len(d[name]) and curr_time - d[name][i] > 3600:
					i += 1
				d[name] = d[name][i:] + [curr_time]
				if len(d[name]) >= 3:
					s.add(name)
		return sorted(list(s))


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def get_diff_minutes(t1, t2):
			(h1, m1) = t1.split(':')
			(h2, m2) = t2.split(':')
			return (int(h2) - int(h1)) * 60 + int(m2) - int(m1)
		res = set()
		store = defaultdict(deque)
		for (time, name) in sorted(zip(keyTime, keyName)):
			while store[name] and get_diff_minutes(store[name][0], time) > 60:
				store[name].popleft()
			store[name].append(time)
			if len(store[name]) >= 3:
				res.add(name)
		return sorted(res)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		result = []
		tracker = {}
		for (person, time) in zip(keyName, keyTime):
			try:
				if tracker[person] and person not in result:
					tracker[person].append(time)
					tracker[person].sort()
					if len(tracker[person]) >= 3:
						for i in range(1, len(tracker[person]) - 1):
							lh = tracker[person][i - 1].split(':')[0]
							ch = tracker[person][i].split(':')[0]
							rh = tracker[person][i + 1].split(':')[0]
							tocheck = [lh, ch, rh]
							if int(lh) <= int(ch) and int(ch) <= int(rh):
								if '23' in tocheck and '00' in tocheck:
									break
								l = int(lh + tracker[person][i - 1].split(':')[1])
								c = int(ch + tracker[person][i].split(':')[1])
								r = int(rh + tracker[person][i + 1].split(':')[1])
								diff = c - l + (r - c)
								if diff <= 100:
									result.append(person)
									break
			except:
				tracker[person] = [time]
		return sorted(result)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		m = collections.defaultdict(set)
		for (n, t) in zip(keyName, keyTime):
			m[n].add(t)
		ans = []
		for name in m:
			added = False
			times = m[name]
			m2 = collections.defaultdict(set)
			for t in times:
				(h, minute) = map(int, t.split(':'))
				m2[h].add(minute)
			for (h, f) in m2.items():
				if len(f) >= 3:
					ans.append(name)
					added = True
					break
			if added:
				continue
			to_minutes = []
			for t in times:
				(h, minute) = map(int, t.split(':'))
				to_minutes.append(h * 60 + minute)
			to_minutes.sort()
			i = 0
			j = 0
			size = 1
			while i < len(to_minutes) and j < len(to_minutes) - 1:
				if to_minutes[j + 1] - to_minutes[i] <= 60:
					j += 1
					if j - i >= 2:
						ans.append(name)
						break
				else:
					i += 1
				j = max(j, i)
		return sorted(ans)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		d = {}
		for i in range(len(keyName)):
			h = int(keyTime[i][0:2])
			m = int(keyTime[i][3:5])
			if keyName[i] in d:
				d[keyName[i]].append(h * 60 + m)
			else:
				d[keyName[i]] = [h * 60 + m]
		ans = []
		for k in list(d.keys()):
			if len(d[k]) < 3:
				continue
			else:
				record = d[k]
				record.sort()
				for i in range(len(record) - 2):
					start = record[i]
					if record[i + 1] - start <= 60 and record[i + 2] - start <= 60:
						ans.append(k)
						break
		ans.sort()
		return ans


from collections import defaultdict

def mins_since_midnight(str_time):
	hours = int(str_time[:2])
	mins = int(str_time[3:])
	return hours * 60 + mins

def difference_mins(str_time1, str_time2):
	return abs(mins_since_midnight(str_time2) - mins_since_midnight(str_time1))

class Solution:

	def alertNames(self, keyName, keyTime):
		alert_names = []
		log = defaultdict(list)
		for (name, time) in zip(keyName, keyTime):
			log[name].append(time)
		for name in log.keys():
			times = log[name]
			sorted_times = sorted(times)
			start = 0
			n = 1
			for i in range(1, len(sorted_times)):
				n += 1
				if difference_mins(sorted_times[start], sorted_times[i]) <= 60:
					if n == 3:
						alert_names.append(name)
						break
				else:
					while difference_mins(sorted_times[start], sorted_times[i]) > 60:
						start += 1
						n -= 1
		return sorted(alert_names)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def oneHourAgo(time1, time2):
			hr_min1 = time1.split(':')
			hr_min2 = time2.split(':')
			if abs(int(hr_min2[0]) - int(hr_min1[0])) > 1 or (abs(int(hr_min2[0]) - int(hr_min1[0])) == 1 and int(hr_min1[1]) < int(hr_min2[1])):
				return True
			else:
				return False
		result = set()
		timeline = defaultdict(list)
		for (name, time) in zip(keyName, keyTime):
			timeline[name].append(time)
		for name in keyName:
			timeline[name].sort()
		for name in keyName:
			q = deque()
			inside_q = 0
			for time in timeline[name]:
				while q and oneHourAgo(q[0], time):
					q.popleft()
					inside_q -= 1
				q.append(time)
				inside_q += 1
				if inside_q >= 3:
					result.add(name)
					break
		result = list(result)
		result.sort()
		return result


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		times = collections.defaultdict(list)
		for (name, time) in zip(keyName, keyTime):
			times[name].append(time)
		res = []

		def withinOneHour(t1, t2):
			(h1, m1) = [int(i) for i in t1.split(':')]
			t1 = h1 * 60 + m1
			(h2, m2) = [int(i) for i in t2.split(':')]
			t2 = h2 * 60 + m2
			return t2 - t1 <= 60
		for name in sorted(times):
			time = sorted(times[name])
			queue = []
			for t in time:
				queue.append(t)
				if not withinOneHour(queue[0], queue[-1]):
					queue.pop(0)
				if len(queue) >= 3:
					res.append(name)
					break
		return res


from sortedcontainers import SortedSet, SortedList
from heapq import heappush, heappop
from datetime import timedelta
from collections import defaultdict, deque

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		users = []
		for (i, kt) in enumerate(keyTime):
			kts = kt.split(':')
			t = timedelta(hours=int(kts[0]), minutes=int(kts[1]))
			users.append((t, keyName[i]))
		users.sort()
		d = defaultdict(deque)
		barier = timedelta(hours=1)
		rez = SortedSet()
		for k in users:
			if len(d[k[1]]) > 0:
				er = d[k[1]][0]
				while k[0] - er > barier and len(d[k[1]]) > 0:
					d[k[1]].popleft()
					if len(d[k[1]]) > 0:
						er = d[k[1]][0]
			d[k[1]].append(k[0])
			if len(d[k[1]]) >= 3:
				rez.add(k[1])
		return list(rez)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def get_minutes(t):
			(h, m) = t.split(':')
			return int(h) * 60 + int(m)

		def is_alert(times):
			lent = len(times)
			if lent < 3:
				return False
			(l, r) = (0, 0)
			for r in range(lent):
				if r - l >= 2 and times[r] - times[l] <= 60:
					return True
				while l < r and times[r] - times[l] > 60:
					l += 1
			return False
		lookup = defaultdict(list)
		for (name, time) in zip(keyName, keyTime):
			lookup[name].append(get_minutes(time))
		alert_list = [name for (name, times) in lookup.items() if is_alert(sorted(times))]
		return sorted(alert_list)


class Solution:

	def timediff(self, t1, t2):
		hdiff = int(t2[:2]) - int(t1[:2])
		mdiff = int(t2[-2:]) - int(t1[-2:])
		fdiff = hdiff * 60 + mdiff
		return fdiff

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		times = dict()
		for i in range(len(keyName)):
			if keyName[i] in list(times.keys()):
				times[keyName[i]].append(keyTime[i])
			else:
				times[keyName[i]] = [keyTime[i]]
		bad = set()
		for name in list(times.keys()):
			t = sorted(times[name])
			for i in range(2, len(t)):
				if self.timediff(t[i - 2], t[i]) <= 60:
					bad.add(name)
					break
		return sorted(list(bad))


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		names = defaultdict(set)
		for (n, t) in zip(keyName, keyTime):
			names[n].add(t)
		for name in names:
			names[name] = sorted(names[name])

		def timediff(t1, t2):
			t1 = list(map(int, t1.split(':')))
			t2 = list(map(int, t2.split(':')))
			h = t2[0] - t1[0]
			m = (t2[1] - t1[1]) / 60
			return h + m
		ans = set()
		for name in names:
			start = 0
			count = 1
			cur = start + 1
			for i in range(cur, len(names[name])):
				diff = timediff(names[name][start], names[name][i])
				print(name, diff)
				if diff <= 1:
					count += 1
					if count == 3:
						ans.add(name)
						break
				else:
					start += 1
		return sorted(ans)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def timeDifference(time1, time2):
			(hr1, min1) = time1.split(':')
			(hr2, min2) = time2.split(':')
			timeDiff = (int(hr2) - int(hr1)) * 60 + int(min2) - int(min1)
			return timeDiff
		res = set()
		rec = collections.defaultdict(list)
		N = len(keyName)
		for i in range(N):
			(hr, minute) = keyTime[i].split(':')
			time = int(hr) * 60 + int(minute)
			rec[keyName[i]].append(time)
		for (key, val) in list(rec.items()):
			if len(val) >= 3:
				sorted_time = sorted(val)
				for i in range(2, len(val)):
					if sorted_time[i] - sorted_time[i - 2] <= 60:
						res.add(key)
						break
		return sorted(list(res))


class Solution:

	def less(self, start, end):
		t1 = int(start[:2]) * 60 + int(start[3:])
		t2 = int(end[:2]) * 60 + int(end[3:])
		if int(end[:2]) < int(start[:2]):
			return True
		return t2 - t1 > 60

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		d = defaultdict(list)
		for i in range(len(keyName)):
			d[keyName[i]].append(keyTime[i])
		w = []
		res = []
		for p in list(d.keys()):
			times = d[p]
			w = []
			for t in sorted(times):
				w.append(t)
				while w and self.less(w[0], t):
					w.pop(0)
				if len(w) >= 3:
					res.append(p)
					break
		res.sort()
		return res


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		mp = {}
		res = []
		for (i, v) in enumerate(keyName):
			if v in mp:
				mp[v].append(keyTime[i])
			else:
				mp[v] = [keyTime[i]]
		for l in mp:
			n = len(mp[l])
			if n < 3:
				continue
			t = mp[l]
			t.sort()
			count = 0
			for i in range(n):
				if i + 2 < n:
					dh = int(t[i + 2].split(':')[0]) - int(t[i].split(':')[0])
					dm = int(t[i + 2].split(':')[1]) - int(t[i].split(':')[1])
					if dh >= 2:
						continue
					elif dh == 1 and dm > 0:
						continue
					else:
						res.append(l)
						break
		res.sort()
		return res

		def hour(hr):
			return int(hr.split(':')[0])

		def minuu(hr):
			return int(hr.split(':')[1])

		def checkTime(self, name) -> bool:
			n = len(mp[name])
			if n < 3:
				return False
			t = mp[name]
			t = t.sort()
			count = 0
			for (i, v) in enumerate(t):
				if i + 2 < n:
					dh = self.hour(t[i + 2]) - self.hour(v)
					dm = self.minuu(t[i + 2]) - self.minuu(v)
					if dh >= 2:
						return False
					elif dh == 1 and dm > 0:
						return False
					else:
						return True


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		d = {}
		n = len(keyName)
		res = []
		(keyTime, keyName) = list(zip(*sorted(zip(keyTime, keyName))))
		for i in range(n):
			if keyName[i] not in d:
				d[keyName[i]] = [keyTime[i], [0], [0], True, False]
			elif not d[keyName[i]][4]:
				min_diff = int(str(keyTime[i][3:])) - int(str(d[keyName[i]][0][3:]))
				hr_diff = int(str(keyTime[i][:2])) - int(str(d[keyName[i]][0][:2]))
				if min_diff < 0:
					min_diff = 60 + min_diff
					hr_diff = hr_diff - 1
				if hr_diff < 0:
					d[keyName[i]] = [keyTime[i], [0], [0], True, False]
				else:
					d[keyName[i]][0] = keyTime[i]
					d[keyName[i]][1].append(hr_diff * 60 + min_diff)
					d[keyName[i]][2].append(d[keyName[i]][1][-1] + d[keyName[i]][1][-2])
					if len(d[keyName[i]][2]) > 2 and d[keyName[i]][2][-1] <= 60:
						d[keyName[i]][4] = True
						res.append(keyName[i])
		return sorted(res)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def checktime(s1, s2):
			h1 = int(s1.split(':')[0])
			m1 = int(s1.split(':')[1])
			h2 = int(s2.split(':')[0])
			m2 = int(s2.split(':')[1])
			if h2 * 60 + m2 - h1 * 60 - m1 <= 60:
				return True
			else:
				return False
		rec = {}
		for i in range(len(keyName)):
			if keyName[i] in rec:
				rec[keyName[i]].append(keyTime[i])
			else:
				rec[keyName[i]] = [keyTime[i]]
		for i in rec.keys():
			rec[i].sort()
		ans = set()
		for i in rec.keys():
			for j in range(len(rec[i]) - 2):
				if checktime(rec[i][j], rec[i][j + 2]):
					ans.add(i)
		ans = list(ans)
		ans.sort()
		return ans


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		kns = defaultdict(list)
		for (i, k1) in enumerate(keyName):
			tok = keyTime[i].split(':')
			mins = int(tok[0]) * 60 + int(tok[1])
			if k1 not in kns:
				kns[k1] = [mins]
			else:
				kns[k1].append(mins)

		def getAlert(tl):
			(start, count) = (0, 1)
			for i in range(1, len(tl)):
				print((tl[i], tl[start]))
				if tl[i] >= tl[start]:
					if tl[i] - tl[start] <= 60:
						count += 1
					else:
						while tl[i] - tl[start] > 60:
							start += 1
						if start == i:
							count = 1
						else:
							count = 2
				else:
					start = i
					count = 1
				if count >= 3:
					return True
			return False
		ans = []
		for (k1, v1) in list(kns.items()):
			v = sorted(v1)
			al = getAlert(v)
			if al:
				ans.append(k1)
		return sorted(ans)


from datetime import timedelta

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		dp = defaultdict(list)
		for i in range(len(keyName)):
			name = keyName[i]
			time = keyTime[i]
			dp[name].append(time)

		def check(ls):
			ls = sorted(ls)
			(start, end) = (0, 0)
			make_date = lambda x: timedelta(hours=int(x[:2]), minutes=int(x[3:]))

			def outer_check(start, end):
				return (make_date(end) - make_date(start)).total_seconds() <= 3600 and int(start[:2]) - int(end[:2]) < 24
			while end < len(ls) and start <= end:
				while end < len(ls) and outer_check(ls[start], ls[end]):
					end += 1
				if end - start >= 3:
					return True
				start += 1
			return False
		res = []
		for (name, t) in list(dp.items()):
			if check(t):
				res.append(name)
		return sorted(res)


from collections import defaultdict

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		res = []
		time = defaultdict(list)
		n = len(keyName)
		lst = sorted(list(zip(keyTime, keyName)))
		for (t, k) in lst:
			if k in res:
				continue
			(h, m) = (int(t[:2]), int(t[-2:]))
			if len(time[k]) >= 2:
				(h_0, m_0) = time[k][-2]
				if (h - h_0) * 60 + (m - m_0) <= 60:
					res.append(k)
				else:
					time[k].append((h, m))
			else:
				time[k].append((h, m))
		return sorted(res)


def time_to_min(etime):
	(hours, minutes) = etime.split(':')
	return int(hours) * 60 + int(minutes)

def add_time_sorted(etime, time_list):
	ii = 0
	while ii < len(time_list) and time_to_min(etime) > time_to_min(time_list[ii]):
		ii += 1
	time_list.insert(ii, etime)

def add_name_sorted(name, alert_list):
	ii = 0
	while ii < len(alert_list) and name > alert_list[ii]:
		ii += 1
	alert_list.insert(ii, name)

def check_for_alert(time_list):
	if len(time_list) <= 2:
		return False
	else:
		delta = []
		for ii in range(0, len(time_list) - 1):
			first_time = time_to_min(time_list[ii])
			second_time = time_to_min(time_list[ii + 1])
			delta.append(second_time - first_time)
			if len(delta) > 1:
				if delta[ii] + delta[ii - 1] <= 60:
					return True
		return False

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		entry = {}
		alert = []
		for ii in range(0, len(keyName)):
			name = keyName[ii]
			etime = keyTime[ii]
			if name not in alert:
				if name not in entry:
					entry[name] = [etime]
				else:
					add_time_sorted(etime, entry[name])
					if check_for_alert(entry[name]):
						add_name_sorted(name, alert)
		return alert


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		name_to_time = collections.defaultdict(list)
		for (name, hour_minute) in zip(keyName, keyTime):
			(hour, minute) = list(map(int, hour_minute.split(':')))
			time = hour * 60 + minute
			name_to_time[name].append(time)
		names = []
		for (name, time_list) in list(name_to_time.items()):
			time_list.sort()
			dq = collections.deque()
			for time in time_list:
				dq.append(time)
				if dq[-1] - dq[0] > 60:
					dq.popleft()
				if len(dq) >= 3:
					names.append(name)
					break
		return sorted(names)


from datetime import datetime

class Solution:

	def alertNames(self, N: List[str], T: List[str]) -> List[str]:
		res = defaultdict(list)
		for i in range(len(N)):
			res[N[i]].append(T[i])
		for i in res:
			res[i] = sorted(res[i])
		final = []
		for emp in res:
			if len(res[emp]) < 3:
				continue
			else:
				(i, j) = (0, 2)
				while j < len(res[emp]):
					a = datetime.strptime(res[emp][i], '%H:%M')
					b = datetime.strptime(res[emp][j], '%H:%M')
					if (b - a).seconds <= 3600:
						final.append(emp)
						break
					else:
						i += 1
						j += 1
		return sorted(final)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		d = collections.defaultdict(list)
		n = len(keyName)
		ans = set()

		def diffTime(h1, h2):
			h = int(h2[:2]) - int(h1[:2])
			m = int(h2[3:]) - int(h1[3:])
			if h >= 2 or h < 0:
				return False
			if h == 1:
				if m <= 0:
					return True
				else:
					return False
			return True
		arr = sorted(zip(keyTime, keyName))
		for i in range(n):
			keyName[i] = arr[i][1]
			keyTime[i] = arr[i][0]
		for i in range(n):
			if keyName[i] in ans:
				continue
			count = 1
			for j in range(len(d[keyName[i]]) - 1, -1, -1):
				if diffTime(d[keyName[i]][j], keyTime[i]):
					count += 1
					if count == 3:
						ans.add(keyName[i])
						break
			d[keyName[i]].append(keyTime[i])
		print(d)
		ans = sorted(ans)
		return ans


from datetime import time, datetime, timedelta

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		size = len(keyName)
		d = {}
		ans = []
		for i in range(size):
			if keyName[i] not in d:
				d[keyName[i]] = [keyTime[i]]
			else:
				d[keyName[i]].append(keyTime[i])
		for j in list(d.keys()):
			temp = len(d[j])
			d[j].sort()
			if temp > 2:
				for k in range(2, temp):
					diff = datetime.strptime(d[j][k], '%H:%M') - datetime.strptime(d[j][k - 2], '%H:%M')
					if diff.days < 0:
						continue
					if diff <= timedelta(hours=1):
						ans.append(j)
						break
		return sorted(ans)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		(ans, n, i, pool) = ([], len(keyName), 0, sorted([[name, time] for (name, time) in zip(keyName, keyTime)]))
		while i < n:
			(j, cur) = (i + 1, collections.deque())
			while j < n and pool[j][0] == pool[i][0]:
				j += 1
			for k in range(i, j):
				time = int(pool[k][1][:2]) * 60 + int(pool[k][1][3:])
				while cur and cur[0] < time - 60:
					cur.popleft()
				if len(cur) > 1:
					ans.append(pool[k][0])
					break
				cur.append(time)
			i = j
		return ans


from collections import defaultdict

def is_within_hour(time_1, time_2):
	[h_1, m_1] = time_1.split(':')
	[h_2, m_2] = time_2.split(':')
	if h_2 == h_1:
		return True
	if int(h_2) == int(h_1) + 1 and m_2 <= m_1:
		return True
	return False

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		logs = defaultdict(list)
		for (name, time) in zip(keyName, keyTime):
			logs[name].append(time)
		output = set()
		for name in logs:
			times = sorted(logs[name])
			for i in range(len(times) - 2):
				if is_within_hour(times[i], times[i + 2]):
					output.add(name)
		return sorted(list(output))


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		d = {}
		for i in range(len(keyName)):
			if keyName[i] in d:
				d[keyName[i]].append(keyTime[i])
			else:
				d[keyName[i]] = [keyTime[i]]
		e = []
		for i in d:
			c = []
			for j in d[i]:
				c.append(int(j[0]) * 600 + int(j[1]) * 60 + int(j[3] + j[4]))
			c.sort()
			if len(c) <= 2:
				continue
			else:
				for k in range(2, len(c)):
					if c[k] - c[k - 2] <= 60:
						e.append(i)
						break
		e.sort()
		return e


class Solution:

	def alertNames(self, keyName, keyTime):
		from collections import defaultdict
		import datetime
		d = defaultdict(list)
		for (name, time) in zip(keyName, keyTime):
			d[name].append(time)
		ans = set()
		for key in d:
			d[key].sort()
			for i in range(len(d[key]) - 2):
				(time1, time2) = (d[key][i], d[key][i + 2])
				FMT = '%H:%M'
				dt1 = datetime.datetime.strptime(time1, FMT)
				dt2 = datetime.datetime.strptime(time2, FMT)
				diff = dt2 - dt1
				if diff.total_seconds() <= 3600:
					ans.add(key)
		return sorted(list(ans))


class Solution:

	def alertNames(self, a: List[str], t: List[str]) -> List[str]:

		def alerted(a):
			for i in range(len(a) - 2):
				if a[i + 2] - a[i] <= 60:
					return True
			return False
		d = defaultdict(list)
		for (name, t) in zip(a, t):
			(h, m) = map(int, t.split(':'))
			d[name].append(h * 60 + m)
		ans = []
		for name in d:
			d[name].sort()
			if alerted(d[name]):
				ans.append(name)
		return sorted(ans)


class Solution:

	def alertNames(self, keyName, keyTime):
		name_to_time = collections.defaultdict(list)
		for (name, hour_minute) in zip(keyName, keyTime):
			(hour, minute) = map(int, hour_minute.split(':'))
			time = hour * 60 + minute
			name_to_time[name].append(time)
		names = []
		for (name, time_list) in name_to_time.items():
			time_list.sort()
			q = collections.deque()
			for t in time_list:
				q.append(t)
				while q[0] < t - 60:
					q.popleft()
				if len(q) > 2:
					names.append(name)
					break
		return sorted(names)


class Solution:

	def alertNames(self, name: List[str], time: List[str]) -> List[str]:
		n = len(time)
		arr = []
		mapper = {}
		for i in range(n):
			(hr, mm) = list(map(int, time[i].split(':')))
			time_in_min = hr * 60 + mm
			worker = name[i]
			if worker in mapper:
				mapper[worker].append(time_in_min)
			else:
				mapper[worker] = [time_in_min]
		for i in mapper:
			value = mapper[i]
			value.sort()
			mapper[i] = value
		for i in mapper:
			value = mapper[i]
			if len(value) >= 3:
				st = 0
				en = 2
				while en < len(value):
					if value[en] - value[st] <= 60:
						arr.append(i)
						break
					en += 1
					st += 1
		if arr == []:
			return []
		arr.sort()
		return arr


import re

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		keyCards = {}
		for i in range(len(keyName)):
			if keyName[i] not in keyCards:
				keyCards[keyName[i]] = []
			hour = int(keyTime[i][0:2])
			minute = int(keyTime[i][3:])
			keyCards[keyName[i]].append(hour * 60 + minute)
		alert_names = []
		for key in list(keyCards.keys()):
			my_times = sorted(keyCards[key])
			for i in range(len(my_times) - 2):
				count = 0
				for j in range(i, len(my_times)):
					if my_times[j] - my_times[i] <= 60:
						count += 1
				if count >= 3:
					alert_names.append(key)
					break
		print(keyCards)
		return sorted(alert_names)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		keys = {}
		for i in range(len(keyName)):
			if keyName[i] in keys:
				keys[keyName[i]].append(keyTime[i])
			else:
				keys[keyName[i]] = [keyTime[i]]
		res = []
		for i in keys.keys():
			time = keys[i]
			if self.emitAlert(time):
				res.append(i)
		return sorted(res)

	def emitAlert(self, t: List[str]) -> bool:
		time_converted = []
		for i in t:
			t = i.split(':')
			time_converted.append(60 * int(t[0]) + int(t[1]))
		time_converted.sort()
		left = 0
		for i in range(len(time_converted)):
			while time_converted[i] - time_converted[left] > 60:
				left += 1
			if i > 0 and time_converted[i] < time_converted[i - 1]:
				left = i
			if i - left >= 2:
				return True
		return False


import bisect

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		d = {}
		for i in range(len(keyName)):
			name = keyName[i]
			time = keyTime[i].split(':')
			time = int(time[0]) * 60 + int(time[1])
			if name not in d:
				d[name] = []
				pass
			bisect.insort_left(d[name], time)
			pass
		ret = set()
		for name in d:
			lst = d[name]
			window = []
			for time in lst:
				now = time
				hour = now - 60
				while len(window) > 0 and window[0] < hour:
					del window[0]
					pass
				window.append(now)
				if len(window) >= 3:
					ret.add(name)
					pass
				pass
			pass
		return list(sorted(ret))


from collections import deque

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		dct = {i: [] for i in set(keyName)}
		for (i, j) in zip(keyName, keyTime):
			j = j.split(':')
			j = int(j[0]) * 60 + int(j[1])
			dct[i].append(j)
		print(dct)

		def check(arr):
			arr = sorted(arr)
			q = deque([arr[0]])
			for i in arr[1:]:
				while q:
					if i > q[0] + 60:
						q.popleft()
					else:
						break
				q.append(i)
				if len(q) >= 3:
					return True
			return False
		res = [i for (i, j) in list(dct.items()) if check(j.copy())]
		res.sort()
		return res


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		times = defaultdict(list)
		for (name, time) in zip(keyName, keyTime):
			times[name].append(time)
		for name in times:
			times[name].sort()
		ans = set()
		for name in times:
			window = defaultdict(deque)
			for time in times[name]:
				(hour, minute) = time.split(':')
				minutes = int(hour) * 60 + int(minute)
				window[name].append(minutes)
				while window[name][0] < minutes - 60:
					window[name].popleft()
				if len(window[name]) > 2:
					ans.add(name)
		return sorted(ans)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		usage = defaultdict(list)
		for (k, name) in enumerate(keyName):
			(hour, minute) = keyTime[k].split(':', 2)
			time_minutes = 60 * int(hour) + int(minute)
			usage[name].append(time_minutes)
		frequent = []
		for name in usage:
			times = sorted(usage[name])
			lo = 0
			hi = 2
			len_times = len(times)
			frequent_name = False
			while hi < len_times and (not frequent_name):
				time_span = times[hi] - times[lo]
				if time_span <= 60:
					frequent.append(name)
					frequent_name = True
				else:
					lo += 1
					hi += 1
		return sorted(frequent)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def toMinutes(time):
			(hour, minute) = time.split(':')
			return int(hour) * 60 + int(minute)
		book = collections.defaultdict(list)
		n = len(keyName)
		res = set()
		for i in range(n):
			q = book[keyName[i]]
			time = toMinutes(keyTime[i])
			heapq.heappush(q, time)
		for (k, v) in list(book.items()):
			window = collections.deque()
			while v:
				window.append(heapq.heappop(v))
				if len(window) >= 3 and window[-1] - window[0] <= 60:
					res.add(k)
				while window and window[-1] - window[0] > 60:
					window.popleft()
		return sorted(res)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		t = [int(s[:2]) * 60 + int(s[3:]) for s in keyTime]
		l = sorted(zip(keyName, t))
		d = collections.defaultdict(list)
		for (i, j) in l:
			d[i] += [j]
		out = []
		for (s, l) in list(d.items()):
			if len(l) < 3:
				continue
			for i in range(2, len(l)):
				if l[i] - l[i - 2] <= 60:
					out.append(s)
					break
		return out


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		m = collections.defaultdict(list)
		for i in range(len(keyName)):
			m[keyName[i]].append(keyTime[i])
		for k in m:
			m[k].sort()
		ts_by_name = collections.defaultdict(list)
		offenders = set()
		for name in m:
			for ts in m[name]:
				tokens = ts.split(':')
				(hour, minute) = (int(tokens[0]), int(tokens[1]))
				ts = hour * 60 + minute
				while len(ts_by_name[name]) > 0 and (ts_by_name[name][0] > ts or ts - ts_by_name[name][0] > 60):
					ts_by_name[name].pop(0)
				ts_by_name[name].append(ts)
				if len(ts_by_name[name]) == 3:
					offenders.add(name)
		return sorted(list(offenders))


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def hm_to_min(s):
			(h, m) = list(map(int, s.split(':')))
			return h * 60 + m
		kt = list(map(hm_to_min, keyTime))
		c = defaultdict(list)
		for (i, k) in enumerate(keyName):
			bisect.insort(c[k], kt[i])
		res = []
		for k in c:
			for i in range(2, len(c[k])):
				if c[k][i] - c[k][i - 2] <= 60:
					res.append(k)
					break
		return sorted(res)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		mp = collections.defaultdict(list)
		for (n, t) in sorted(zip(keyName, keyTime)):
			minutes = int(t[:2]) * 60 + int(t[3:])
			mp[n].append(minutes)
		ret = []
		for (n, t) in list(mp.items()):
			if len(t) < 2:
				continue
			i = 0
			for (j, val) in enumerate(t):
				while val - t[i] > 60:
					i += 1
				if j - i >= 2:
					ret.append(n)
					break
		return ret


from collections import defaultdict

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def with_in_one_hour(t1, t3):
			(h1, s1) = t1.split(':')
			(h3, s3) = t3.split(':')
			return h1 == h3 or (int(h3) - int(h1) == 1 and s1 >= s3)
		res = []
		d = defaultdict(list)
		for (n, t) in zip(keyName, keyTime):
			d[n].append(t)
		for (n, t_list) in list(d.items()):
			if len(t_list) > 2:
				t_list.sort()
				for (i, t) in enumerate(t_list[2:]):
					if with_in_one_hour(t_list[i], t_list[i + 2]):
						res.append(n)
						break
		return sorted(res)


class Worker(object):

	def __init__(self, name):
		self.name = name
		self.minutes = []

	def add(self, time):
		(h, m) = tuple(time.split(':'))
		(h, m) = (int(h), int(m))
		self.minutes.append(h * 60 + m)

	def is_alert(self):
		self.minutes.sort()
		for (i, lower) in enumerate(self.minutes):
			upper = lower + 60
			j = bisect.bisect_right(self.minutes, upper)
			if j - i >= 3:
				return True
		return False

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		workers = {}
		for (name, time) in zip(keyName, keyTime):
			if name not in workers:
				workers[name] = Worker(name)
			workers[name].add(time)
		ans = []
		for (name, worker) in workers.items():
			if worker.is_alert():
				ans.append(name)
		return sorted(ans)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		d = defaultdict(list)
		keylist = list(zip(keyName, keyTime))
		keylist = sorted(keylist, key=lambda x: x[1])
		ans = set()
		for (name, t) in keylist:
			if len(d[name]) < 3:
				d[name].append(t)
			elif len(d[name]) == 3:
				d[name].pop(0)
				d[name].append(t)
			if len(d[name]) == 3:
				begin = d[name][0].split(':')
				end = d[name][2].split(':')
				if begin[0] == end[0]:
					ans.add(name)
				elif int(begin[0]) + 1 == int(end[0]) and int(begin[1]) >= int(end[1]):
					ans.add(name)
		ans = list(ans)
		ans.sort()
		return ans


def time2num(t):
	(h, m) = t.split(':')
	return [int(h), int(m)]

def check_1hour(t1, t2):
	if t1[0] == t2[0]:
		return True
	if t2[0] - t1[0] == 1 and t2[1] <= t1[1]:
		return True
	return False

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		dt = {}
		for (k, v) in zip(keyName, keyTime):
			if k in dt:
				dt[k].append(v)
			else:
				dt[k] = [v]
		res = []
		for (k, v) in list(dt.items()):
			if len(v) < 3:
				continue
			if Solution.find_time(v):
				res.append(k)
		return sorted(res)

	@staticmethod
	def find_time(list_time):
		l2 = list(map(time2num, list_time))
		print(l2)
		l2 = sorted(l2)
		n = len(list_time)
		for i in range(n - 2):
			if check_1hour(l2[i], l2[i + 2]):
				return True
		return False


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		t = [int(s[:2]) * 60 + int(s[3:]) for s in keyTime]
		l = sorted(zip(keyName, t))
		d = collections.defaultdict(list)
		for (i, j) in l:
			d[i] += [j]
		return [s for (s, l) in list(d.items()) if any((j - i <= 60 for (i, j) in zip(l[:-2], l[2:])))]


class Solution:

	def alertNames(self, name_list: List[str], time: List[str]) -> List[str]:
		time_list = []
		for ts in time:
			(h, m) = list(map(int, ts.split(':')))
			time_list.append(h * 60 + m)
		res = set()
		A = list(sorted(zip(name_list, time_list)))
		for (i, (name, t)) in enumerate(A):
			if i + 2 < len(name_list) and name == A[i + 2][0] and (t >= A[i + 2][1] - 60):
				res.add(name)
		return sorted(res)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		doc = collections.defaultdict(collections.deque)
		res = set()
		for (name, time) in sorted(zip(keyName, keyTime), key=lambda x: x[1]):
			while doc[name] and self.delta_time(time, doc[name][0]) > 60:
				doc[name].popleft()
			doc[name].append(time)
			if len(doc[name]) >= 3:
				res.add(name)
		return sorted(list(res))

	def delta_time(self, t1, t2):
		(h1, m1) = t1.split(':')
		(h2, m2) = t2.split(':')
		return int(h1) * 60 + int(m1) - (int(h2) * 60 + int(m2))


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		from collections import defaultdict
		name_time = defaultdict(list)
		access_violations = set()
		for (n, t) in zip(keyName, keyTime):
			name_time[n].append(t)
		for (k, v) in list(name_time.items()):
			if len(v) < 2:
				continue
			v.sort()
			if self.checkViolation(v):
				access_violations.add(k)
		access_violations = list(access_violations)
		access_violations.sort()
		return access_violations

	def checkViolation(self, access_times):
		from collections import deque
		access_time = deque()
		for t in access_times:
			access_time.append(t)
			if len(access_time) > 1:
				t_start = access_time[0]
				t_end = t
				if self.diff(t_start, t_end):
					access_time.popleft()
				if len(access_time) >= 3:
					return True
		return False

	def diff(self, t_start, t_end):
		(h1, m1) = t_start.split(':')
		(h2, m2) = t_end.split(':')
		if int(h2) - int(h1) >= 2:
			return True
		if int(h2) - int(h1) == 0:
			return False
		minutes = 60 - int(m1) + int(m2)
		if minutes <= 60:
			return False
		else:
			return True


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		keytime_table = dict()
		for idx in range(len(keyName)):
			name = keyName[idx]
			time = keyTime[idx]
			keytime_table.setdefault(name, []).append(time)
		ans = []
		for name in list(keytime_table.keys()):
			time_list = keytime_table[name]
			time_list.sort()
			l = 0
			r = 0
			(hour, minute) = time_list[0].split(':')
			l_minutes = int(hour) * 60 + int(minute)
			while l <= r and r < len(time_list):
				r_time = time_list[r]
				(hour, minute) = r_time.split(':')
				r_minutes = int(hour) * 60 + int(minute)
				if r_minutes - l_minutes <= 60:
					if r - l >= 2:
						ans.append(name)
						break
					r += 1
				else:
					l += 1
					if l > r:
						r += 1
					l_time = time_list[l]
					(hour, minute) = l_time.split(':')
					l_minutes = int(hour) * 60 + int(minute)
		ans.sort()
		return ans


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		x = defaultdict(list)
		for i in range(len(keyName)):
			time = int(keyTime[i][0:2] + keyTime[i][3:5])
			x[keyName[i]].append(time)
		threePeat = []
		for (key, value) in list(x.items()):
			if len(value) >= 3:
				value = sorted(value)
				for i in range(len(value) - 2):
					if value[i + 1] - 100 <= value[i] and value[i + 2] - 100 <= value[i]:
						threePeat.append(key)
						break
		return sorted(threePeat)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		from collections import defaultdict
		key_pairs = [(time, name) for (name, time) in zip(keyName, keyTime)]
		key_pairs.sort()
		keys = defaultdict(list)
		names = set()
		for pair in key_pairs:
			(time, name) = pair
			if name in names:
				continue
			keys[name].append(time)
			if len(keys[name]) < 3:
				continue
			(hour, minute) = time.split(':')
			(hour, minute) = (int(hour), int(minute))
			first_access_time = keys[name][-3]
			(first_hour, first_minute) = first_access_time.split(':')
			(first_hour, first_minute) = (int(first_hour), int(first_minute))
			if hour - first_hour <= 1:
				if hour - first_hour == 1:
					if minute - first_minute > 0:
						continue
					else:
						names.add(name)
				else:
					names.add(name)
		res = list(names)
		res.sort()
		return res


from collections import defaultdict

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		workers = defaultdict(list)
		tup = [[keyTime[i], keyName[i]] for i in range(len(keyTime))]
		for i in range(len(keyName)):
			workers[tup[i][1]].append(tup[i][0])
		answer = []
		for (worker, times) in list(workers.items()):
			(i, j) = (0, 0)
			stimes = sorted(times)
			while j < len(stimes):
				hh1 = int(stimes[i][:2])
				hh2 = int(stimes[j][:2])
				mm1 = int(stimes[i][3:])
				mm2 = int(stimes[j][3:])
				if hh1 == hh2 or (abs(hh1 - hh2) == 1 and mm2 + (60 - mm1) <= 60):
					if j - i + 1 == 3:
						answer.append(worker)
						break
					j += 1
				else:
					i += 1
		return sorted(answer)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def time(strt):
			(h, m) = strt.split(':')
			h = h[1:] if h[0] == '0' else h
			m = m[1:] if m[0] == '0' else m
			return int(h) * 60 + int(m)
		use = collections.defaultdict(lambda : collections.deque(maxlen=3))
		ans = set()
		for (n, t) in sorted([(n, t) for (n, t) in zip(keyName, keyTime)], key=lambda x: x[1]):
			use[n].append(t)
			if len(use[n]) == 3 and abs(time(use[n][-1]) - time(use[n][0])) <= 60:
				print(n, use[n])
				ans.add(n)
		return sorted(ans)


def time_diff(S1, S2):
	(h1, h2, m1, m2) = (int(S1[:2]), int(S2[:2]), int(S1[3:5]), int(S2[3:5]))
	h_diff = h2 - h1
	m_diff = m2 - m1
	return (h2 - h1) * 60 + m2 - m1
from collections import defaultdict

class Solution:

	def alertNames(self, keyName, keyTime):
		ans = set()
		names = defaultdict(list)
		time_name = sorted(list(zip(keyTime, keyName)))
		for (time, name) in time_name:
			names[name].append(time)
			if len(names[name]) >= 3 and time_diff(names[name][-3], names[name][-1]) <= 60:
				ans.add(name)
		print(names)
		return sorted(list(ans))


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		times = defaultdict(list)
		for i in range(len(keyName)):
			time = int(keyTime[i][:2] + keyTime[i][3:5])
			times[keyName[i]].append(time)
		print(times)
		threes = []
		for (key, value) in times.items():
			if len(value) >= 3:
				value = sorted(value)
				for i in range(len(value) - 2):
					if value[i + 1] - 100 <= value[i] and value[i + 2] - 100 <= value[i]:
						threes.append(key)
						break
		return sorted(threes)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def time_to_minutes(time):
			(h, m) = time.split(':')
			return int(m) + 60 * int(h)

		def time_difference(t1, t2):
			return t2 - t1
		keyTime = [time_to_minutes(t) for t in keyTime]
		(keyTime, keyName) = zip(*sorted(zip(keyTime, keyName)))
		usage = collections.defaultdict(collections.deque)
		res = set()
		for (name, time) in zip(keyName, keyTime):
			if name in res:
				continue
			if len(usage[name]) == 2:
				if time_difference(usage[name][0], time) <= 60:
					res.add(name)
				usage[name].popleft()
				usage[name].append(time)
			else:
				usage[name].append(time)
		return sorted(res)


import datetime

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def time_to_sec(time):
			[hours, minutes] = [int(x) for x in time.split(':')]
			x = datetime.timedelta(hours=hours, minutes=minutes)
			return x.seconds
		dic = {}
		sec = []
		for i in range(len(keyTime)):
			sec.append(time_to_sec(keyTime[i]))
		name = keyName
		for i in range(len(name)):
			if name[i] not in dic:
				dic[name[i]] = [sec[i]]
			else:
				dic[name[i]].append(sec[i])
		for (key, value) in list(dic.items()):
			value.sort()
		ans = []
		for (key, value) in list(dic.items()):
			if len(value) >= 3:
				count = 1
				i = 0
				j = 1
				while j < len(value):
					if value[j] - value[i] <= 3600:
						if value[j] - value[i] != 0:
							count += 1
						j += 1
					else:
						i += 1
						count = 1
					if count == 3:
						ans.append(key)
		return sorted(list(set(ans)))


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		record = {}

		def to_mininute(time):
			(h, m) = [int(t) for t in time.split(':')]
			return h * 60 + m
		keyTime = list(map(to_mininute, keyTime))
		data = list(zip(keyTime, keyName))
		data.sort()
		for (time, name) in data:
			if name not in record:
				record[name] = []
			record[name].append(time)
		ans = set()
		for (name, times) in list(record.items()):
			print((name, times))
			l = len(times)
			for i in range(2, l):
				if times[i] - times[i - 2] <= 60:
					ans.add(name)
					break
		return sorted(list(ans))


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		ans = set()
		emp = defaultdict(list)
		for (name, time) in zip(keyName, keyTime):
			(h, m) = list(map(int, time.split(':')))
			t = h * 60 + m
			emp[name].append(t)
		for (p, ts) in list(emp.items()):
			ts.sort()
			tmp = deque(maxlen=3)
			for t in ts:
				tmp.append(t)
				if len(tmp) == 3 and tmp[0] + 60 >= tmp[-1]:
					ans.add(p)
					continue
		return sorted(ans)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		key_uses = list(sorted(zip(keyName, keyTime)))
		alerts = set()
		uses_by_user = collections.defaultdict(deque)
		for (user, time) in key_uses:
			(hr, mn) = time.split(':')
			tm = int(hr) * 60 + int(mn)
			uses_by_user[user].append(tm)
			print(uses_by_user[user][0])
			while uses_by_user[user][0] < tm - 60:
				uses_by_user[user].popleft()
			if len(uses_by_user[user]) > 2:
				alerts.add(user)
		return sorted(list(alerts))


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		arr = sorted(zip(keyName, keyTime))
		person = arr[0][0]
		queue = []
		res = []
		flag = False

		def diff(t1, t2):
			t1 = int(t1[:2]) * 60 + int(t1[3:])
			t2 = int(t2[:2]) * 60 + int(t2[3:])
			return t2 - t1
		for i in range(len(arr)):
			if arr[i][0] != person:
				person = arr[i][0]
				queue = [arr[i][1]]
				flag = False
			else:
				if flag == True:
					continue
				queue.append(arr[i][1])
				while diff(queue[0], arr[i][1]) > 60:
					queue.pop(0)
				if len(queue) >= 3:
					res.append(person)
					flag = True
		return res


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		ar = sorted(zip(keyTime, keyName))
		d = dict()
		ans = set()
		n = len(ar)
		(i, j) = (0, 0)
		while i < n:
			(time, name) = ar[i]
			(hour, minute) = map(int, time.split(':'))
			timeLimit = str(hour - 1).zfill(2) + ':' + str(minute).zfill(2)
			while j < i and ar[j][0] < timeLimit:
				d[ar[j][1]] -= 1
				j += 1
			d[name] = 1 + d.get(name, 0)
			if d[name] >= 3:
				ans.add(name)
			i += 1
		return sorted(ans)


from collections import deque

class TimeTracker:

	def __init__(self):
		self.users = defaultdict(deque)

	def add(self, name, time):
		self.users[name].append(time)
		while self.users[name][-1] - self.users[name][0] > 60:
			self.users[name].popleft()
		if len(self.users[name]) >= 3:
			return True
		return False

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		alerts = set()
		tracker = TimeTracker()
		names = sorted([(name, convert_time(time)) for (name, time) in zip(keyName, keyTime)])
		for (name, time) in names:
			if tracker.add(name, time):
				alerts.add(name)
		return sorted(alerts)

def convert_time(timestamp):
	(hours, minutes) = timestamp.split(':')
	time = int(hours) * 60 + int(minutes)
	return time


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		M = defaultdict(list)
		for (i, j) in zip(keyName, keyTime):
			bisect.insort(M[i], j)
		keys = sorted(M.keys())
		res = []

		def getMins(time):
			return int(time[:2]) * 60 + int(time[3:])
		for key in keys:
			for i in range(2, len(M[key])):
				curr = M[key][i]
				prev1 = M[key][i - 2]
				if getMins(curr) - getMins(prev1) <= 60:
					res.append(key)
					break
		return res


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		res = set()
		d = collections.defaultdict(list)
		for (key, time) in zip(keyName, keyTime):
			hour = int(time[:2])
			minute = int(time[3:])
			d[key].append(60 * hour + minute)
		for (key, times) in d.items():
			if key not in res:
				times.sort()
				q = deque()
				for time in times:
					q.append(time)
					while q and (q[-1] - q[0]) % (24 * 60) > 60:
						q.popleft()
					if len(q) >= 3:
						res.add(key)
						break
		return sorted(res)


class Solution:

	def alertNames(self, keyName: 'List[str]', keyTime: 'List[str]') -> 'List[str]':
		N = len(keyName)
		arr = []
		for i in range(N):
			t = int(keyTime[i][:2]) * 60 + int(keyTime[i][3:])
			arr.append([t, keyName[i]])
		arr.sort()
		i = 0
		counter = collections.Counter()
		res = set()
		for j in range(N):
			while arr[j][0] - arr[i][0] > 60:
				counter[arr[i][1]] -= 1
				i += 1
			counter[arr[j][1]] += 1
			if counter[arr[j][1]] >= 3:
				res.add(arr[j][1])
		return sorted(list(res))


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		keyTime = [time.split(':') for time in keyTime]
		keyTime = [[int(time[0]), int(time[1])] for time in keyTime]
		(lru, res) = (defaultdict(deque), set())
		for (name, time) in sorted(zip(keyName, keyTime), key=lambda k: k[1]):
			if name in res:
				continue
			lru[name].append(time)
			if len(lru[name]) > 2:
				(front, back) = (lru[name][0], lru[name][-1])
				if back[0] == front[0] or (back[0] - front[0] == 1 and back[1] <= front[1]):
					res.add(name)
				else:
					lru[name].popleft()
		return sorted(list(res))


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		from collections import defaultdict
		d = defaultdict(list)
		n = len(keyName)
		for i in range(n):
			time = int(keyTime[i][:1] + keyTime[i][3:])
			d[keyName[i]].append(int(keyTime[i][:2] + keyTime[i][3:]))
		ans = []
		for name in d:
			d[name].sort()
			for i in range(len(d[name]) - 2):
				if d[name][i + 2] - d[name][i] <= 100:
					ans.append(name)
					break
		print(d)
		return sorted(ans)


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		n = len(keyName)
		lst = [0] * n
		for i in range(n):
			(a, b) = keyTime[i].split(':')
			st = float(a + '.' + b)
			lst[i] = [keyName[i], st]
		lst.sort()
		i = 0
		ans = []
		while i < n:
			name = lst[i][0]
			minn = lst[i][1]
			lst2 = []
			while i < n and lst[i][0] == name:
				lst2.append(lst[i][1])
				i += 1
			lst2.sort()
			if len(lst2) >= 3:
				foo = 0
				for k in range(len(lst2) - 2):
					if float(format(lst2[k + 2] - lst2[k], '.2f')) <= 1.0:
						foo = 1
				if foo == 1:
					ans.append(name)
		ans.sort()
		return ans


class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
		pairs = []
		for i in range(len(keyName)):
			pairs.append((keyName[i], self.getMinutes(keyTime[i])))
		pairs.sort()
		print(pairs)
		i = 0
		res = []
		while i + 2 < len(pairs):
			if pairs[i + 2][0] == pairs[i][0]:
				name = pairs[i][0]
				print(name)
				print(pairs[i + 1][1], pairs[i][1] + 60)
				print(pairs[i + 2][1], pairs[i][1] + 60)
				if pairs[i + 1][1] <= pairs[i][1] + 60 and pairs[i + 2][1] <= pairs[i][1] + 60:
					res.append(pairs[i][0])
					while i < len(pairs) and pairs[i][0] == name:
						i += 1
					i -= 1
			i += 1
		return res

	def getMinutes(self, time):
		(hh, mm) = time.split(':')
		return int(hh) * 60 + int(mm)


from collections import defaultdict
from collections import deque

class Solution:

	def alertNames(self, key_name, key_time):
		time_name = []
		for (name, time_) in zip(key_name, key_time):
			(hour_str, minute_str) = time_.split(':')
			(hour, minute) = (int(hour_str), int(minute_str))
			time_name.append((60 * hour + minute, name))
		time_name.sort()
		mapping = defaultdict(deque)
		res = set()
		for (time_, name) in time_name:
			curr = mapping[name]
			while curr and time_ - curr[0] > 60:
				curr.popleft()
			curr.append(time_)
			if len(curr) >= 3:
				res.add(name)
		return sorted(res)


from collections import Counter

class Solution:

	def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:

		def _convertTime(x):
			h = int(x[0:2])
			m = int(x[3:5])
			t = h * 60 + m
			return t
		keyTime = [_convertTime(el) for el in keyTime]
		keys = list(zip(keyTime, keyName))
		keys = sorted(keys)
		people = {}
		for key in keys:
			if key[1] in people:
				people[key[1]].append(key)
			else:
				people[key[1]] = [key]
		ans = []
		for (person, keys) in list(people.items()):
			q = []
			for key in keys:
				time = key[0]
				q.append(time)
				while q[0] + 60 < q[-1]:
					q.pop(0)
				if len(q) >= 3:
					ans.append(key[1])
					break
		return sorted(ans)