57. Insert Interval

The input is already sorted and non-overlapping, so there's nothing to sort — one linear pass does it, split into three clean phases. Phase 1: intervals entirely left of newInterval (their end below…