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
This problem combines interval merging with interval subtraction. First, sort the meetings by start time and scan them linearly to merge any overlapping intervals. Then, for each merged meeting interval, remove the portions that overlap with the DNS ranges, splitting the interval when necessary. The key implementation details are handling boundary overlap correctly and applying a clean sweep over sorted intervals.
