今天在面试的时候得到了这个。想出了一个O(N*logN)
解决方案。想知道是否有O(N)
可用解决方案...
概述:将各个时间表合并到一个列表中intervals
--> 按间隔的开始时间排序 --> 如果交叉则合并相邻间隔 --> 现在返回可用性很容易。
import unittest
# O(N * logN) + O(2 * N) time
# O(3 * N) space
def find_available_times(schedules):
ret = []
intervals = [list(x) for personal in schedules for x in personal]
intervals.sort(key=lambda x: x[0], reverse=True) # O(N * logN)
tmp = []
while intervals:
pair = intervals.pop()
if tmp and tmp[-1][1] >= pair[0]:
tmp[-1][1] = max(pair[1], tmp[-1][1])
else:
tmp.append(pair)
for i in range(len(tmp) - 1):
ret.append([tmp[i][1], tmp[i + 1][0]])
return ret
class CalendarTests(unittest.TestCase):
def test_find_available_times(self):
p1_meetings = [
( 845, 900),
(1230, 1300),
(1300, 1500),
]
p2_meetings = [
( 0, 844),
( 845, 1200),
(1515, 1546),
(1600, 2400),
]
p3_meetings = [
( 845, 915),
(1235, 1245),
(1515, 1545),
]
schedules = [p1_meetings, p2_meetings, p3_meetings]
availability = [[844, 845], [1200, 1230], [1500, 1515], [1546, 1600]]
self.assertEqual(
find_available_times(schedules),
availability
)
def main():
unittest.main()
if __name__ == '__main__':
main()