Trace intervals = [[1,2],[3,5],[6,7]], newInterval = [4,6].
Phase 1: intervals before [4,6].
- [1,2]: end=2 < 4. Add [1,2]. Result: [[1,2]].
Phase 2: overlapping intervals.
- [3,5]: 3 < 6 and 5 >= 4. Overlaps! Merge: new = [min(3,4), max(5,6)] = [3,6].
- [6,7]: 6 <= 6 and 7 >= 4. Overlaps! Merge: new = [min(3,6), max(6,7)] = [3,7].
Add merged [3,7]. Result: [[1,2],[3,7]].
Phase 3: no more intervals.
Final: [[1,2],[3,7]].
time, space for output.