Interval”
Since we only have to insert one interval here, and our intervals are already sorted, we can do this in O(n) time by thinking about it as having three sections:
- All intervals that come before the new interval (we’ll call this left)
- All intervals that come after the interval (we’ll call this right).
- All intervals that overlap with the new interval
- If the interval’s end time is before the new interval’s start time, we know that this interval comes before.
- If the interval’s start time is after the new interval’s end time, we know that this interval comes after.
- Otherwise, we have to do some kind of merge. Since we want to subsume all intervals, we will take the minimum starting time and the maximum ending time.
def main(intervals, newInterval):
left = []
right = []
mid = [newInterval[0], newInterval[1]]
for interval in intervals:
if interval[1] < start:
left.append(interval)
elif interval[0] > end:
right.append(interval)
else:
mid[0] = min(mid[0], interval[0])
mid[1] = max(mid[1], interval[1])
return left + [mid] + right