Meeting Rooms
你会得到一个由两个数组表示的会议列表：会议 i 从 starts[i] 开始，到 ends[i] 结束。一个人想参加所有会议，因此不能有两场会议重叠。一场会议可以恰好在另一场会议结束时开始。如果这个人可以参加每场会议，就返回 true，否则返回 false。
函数
- startsinteger-array
- 每次会议的开始时间
- endsinteger-array
- 每场会议的结束时间，与其开始时间位于相同的索引处
- 返回值boolean
- 如果没有两场会议重叠，则为 true，否则为 false
约束条件
1 ≤ starts.length == ends.length ≤ 50000 ≤ starts[i] < ends[i] ≤ 106- 会议没有排序。两场会议可能完全相同。
示例
- 输入
- starts = [9, 13, 10]ends = [10, 15, 12]
- 输出
- true
- 解释
- 按时间顺序，会议分别是 9 点到 10 点、10 点到 12 点和 13 点到 15 点。第二场会议在第一场结束的那一刻开始，这是允许的，所以答案是
true。
- 输入
- starts = [1, 4, 7]ends = [5, 6, 8]
- 输出
- false
- 解释
- 从 1 到 5 的会议在 4 点时仍在进行，而从 4 到 6 的会议此时开始，所以答案是
false。
进阶
如果会议是逐个预订的，怎样才能在不重新排序所有内容的情况下，用 O(log n) 检查每个新预订是否与日程冲突？
提示
逐个打开提示，每个都会多透露一点。
两场时间冲突的会议必然有一段时间重叠。你可以按什么顺序列出这些会议，让相邻的会议之间出现时间冲突？
按开始时间排列会议。这样，每场会议只可能与紧挨着它之前的会议冲突：如果它的开始时间晚于那场会议的结束时间，也就晚于所有更早会议的结束时间。
按开始时间排序，并让每个开始时间与对应的结束时间保持配对。遍历排序后的列表，将每个开始时间与前一个会议的结束时间进行比较。如果开始时间更早，就表示会议冲突；如果开始时间与结束时间相同，则没有问题。
题解
检查每一对会议，找出所有冲突需要 O(n²)。改为按开始时间排序：这样，会议只可能与排序后相邻的会议冲突，因此每个会议只需比较一次。
比较每一对
结果正确，但无法在最大的测试中运行完毕
思路
如果两个会议中，每个会议都在另一个会议结束前开始，它们就会冲突：对于 1 到 5 和 4 到 6，1 早于 6，4 早于 5。两边都使用严格的 <，这样 9 到 10 和 10 到 12 可以首尾相接而不冲突。检查每一对会议，并在首次发现冲突时返回 false。
当 n = 5000 时，大约有 1250 万对会议，而没有冲突的日程会让你检查所有会议对。
算法
- 对于每个索引
i，以及它之后的每个索引j： - 如果
starts[i] < ends[j]且starts[j] < ends[i]，这两场会议就有重叠：返回false。 - 如果没有任何一对会议重叠，则返回
true。
def canAttendMeetings(starts, ends):
n = len(starts)
for i in range(n):
for j in range(i + 1, n):
# two meetings clash when each one starts before the other ends
if starts[i] < ends[j] and starts[j] < ends[i]:
return False
return True按起点排序并检查相邻项
思路
按开始时间对会议排序，并让每个开始时间与它对应的结束时间保持配对。如果目前还没有发现冲突，那么到目前为止的会议就构成了一条链，每场会议都在前一场结束时或之后开始。因此，新会议前面的那场会议结束得最晚，而新会议如果在它结束时或之后开始，就不会与任何会议重叠。如果新会议在它结束前开始，就会发生冲突。
开始时间相同的会议一定会冲突，因为每场会议至少持续一个单位时间，同样的检查也能发现这种情况。排序的时间复杂度为 O(n log n)，遍历的时间复杂度为 O(n)，会议配对副本占用 O(n) 空间。
算法
- 将每个开始时间与对应的结束时间配对。
- 按开始时间对配对结果排序。
- 对于第一场会议之后的每场会议，将其开始时间与前一场会议的结束时间进行比较。
- 如果开始时间更小，则返回
false。 - 循环结束后，返回
true。
def canAttendMeetings(starts, ends):
meetings = sorted(zip(starts, ends)) # by start time
for i in range(1, len(meetings)):
# a meeting must not start before the one right before it ends
if meetings[i][0] < meetings[i - 1][1]:
return False
return True
易错点和边界情况
- 对
starts排序，却让ends保持输入顺序。每个结束时间必须和它对应的开始时间一起移动，否则你比较的开始时间和结束时间就可能属于不同的会议。 - 使用
≤，而不是<。从 9 点到 10 点和从 10 点到 12 点的会议只是相接，这种情况下答案是true。 - 按输入顺序比较相邻项。输入并没有排序：1 到 5、7 到 8、4 到 6，这些相邻项之间没有冲突，但第一项和最后一项重叠。
- 只用一个条件编写会议对的检查，例如
starts[j] < ends[i]。按此顺序，时间为 5 到 6 和 0 到 1 的两个会议，0 < 6会报告并不存在的冲突。
常见问题3
会议室问题的时间复杂度是多少？
按开始时间对会议排序的时间复杂度为 O(n log n)，比较相邻会议的遍历时间复杂度为 O(n)，因此总时间复杂度为 O(n log n)。比较每一对会议的时间复杂度为 O(n²)。
结束时间和开始时间相同的会议算重叠吗？
这道题中不是这样：一个会议可以在另一个会议结束的那一刻开始，因此检查条件是严格的 start < previous end。如果不允许会议时间相接，条件就会变成 start ≤ previous end。
如何找到所需的最少会议室数量？
将开始时间和结束时间分别排序成两个列表，然后同时遍历它们：每个开始时间都需要一间房，每个不晚于下一个开始时间的结束时间都会腾出一间房。房间同时使用的最大数量就是答案。这道题要判断一间房是否够用。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def canAttendMeetings(starts, ends):
# 在这里编写代码测试 #1
测试 #2
参数
starts = [9, 13, 10] ends = [10, 15, 12]
预期输出
true