Insert Interval

**Problem Statement:** You are given an array of non-overlapping intervals `intervals` where `intervals[i] = [starti, endi]` represent the start and the end of the `i`th interval and `intervals` is sorted in ascending order by `starti`. You are also given an interval `newInterval`. Insert `newInterval` into `intervals` such that `intervals` is still sorted in ascending order by `starti` and `intervals` still does not have any overlapping intervals. **Hint / Expected Approach:** Single-pass before/overlap/after regions **Edge Cases to Consider:** - (1) New interval before all - (2) Absorbs all intervals - (3) Empty input list