Can we assume the input is sorted or not? You can sort by the start time of each interval.
Merge the overlapping meetings with a loop over the meetings. Then, for each merged interval, remove the part that overlaps with the DNS time ranges.
How would you merge the second and third meetings [12, 30] and [22, 35]?
12 starts before 22, so we need to check if they overlap. The end of the first is 30 > 22, so we need to merge them. The new interval becomes [12, 35].
Meetings: [(1, 7, 1), (5, 10, 2), (12, 30, 1), (22, 30, 1), (40, 50, 1), (60, 70, 1)]
DNS: [(18, 25), (20, 28), (65, 75)]# Only merge the meeting
这道题本质上是“区间合并 + 区间裁剪”的组合题。先按起始时间排序，把重叠的 meeting 合并成若干不相交区间；判断方式很直接：如果当前区间的起点不大于上一个区间的终点，就更新终点为两者的最大值。随后再把每个合并后的会议区间与 DNS 时间段做差集处理，删掉被 DNS 覆盖的部分，必要时一个会议区间可能会被切成左右两段。整体思路通常使用排序、线性扫描和双指针 / 区间遍历，重点是正确处理边界重叠与多段 DNS 覆盖。
正文完
