Answer: Oracle OA Question 2024 June | Intervals & Arrays | on-campus

Solution: Insert Interval — Linear Partition Approach Since the initial intervals are already sorted, we can solve this in a single linear scan O(N) without needing to sort again: Left Part: Add all intervals that end before the new interval starts (no overlap). These intervals satisfy intervals[i][1] < newInterval[0]. Merge Overlaps: While there is an overlap (the current interval starts before or at the end of the new interval, satisfying intervals[i][0] <= newInterval[1]), merge them by expanding the bounds: newInterval[0] ...