57. Insert Interval
Medium — Three-phase Linear Scan
Apply
Play
Pause
Step
Reset
Speed:
Slow
Normal
Fast
Very Fast
Press "Play" or "Step" to walk through the algorithm.
Step
0 / 0
Phase
--
cur
[—,—]
Output Length
0
Existing intervals
cur (newInterval)
Absorbing
Merged into output
Algorithm Complexity
Append + Re-merge
O(n log n)
Time / Space: O(n log n) / O(n)
Three-Phase Linear
O(n)
Time / Space: O(n) / O(n)
Binary Boundaries
O(n) copy + O(log n) lookup
Time / Space: O(n) / O(n)