Pattern visualizer
Insert Interval
Because the input list is already sorted and non-overlapping, a new interval can only ever collide with a contiguous run of existing ones — never scattered ones. So one linear pass does it: copy every interval that ends before the new one starts untouched, absorb every interval that overlaps into a single growing merged interval, then copy whatever's left. Animated on: intervals = [[1,3],[6,9]], newInterval = [2,5] — insert and merge, keeping the list sorted and disjoint..
One pass: before, merge, after
time O(n)space O(n)step 1 / 4
[1,3]
[0][6,9]
[1]line 2
intervals=[1,3],[6,9], inserting [2,5]. Since intervals arrive sorted by start, we only need one pass.
Pseudocode
1FUNCTION insert(intervals, newInterval):2 result = empty list3 WHILE the end of intervals[i] < the start of newInterval:4 append intervals[i] to result; move i one step right (no overlap yet)5 WHILE the start of intervals[i] <= the end of newInterval:6 newInterval = merge of newInterval and intervals[i]; move i one step right7 append newInterval to result8 WHILE i < n: append intervals[i] to result; move i one step right
← / → step · space play · Home restart