Hello and welcome back brave human being.

Before we delve into this problem, I want to remind you that doing a LeetCode problem is liking going to the gym, a mental gym. Every LeetCode problem you solve equals a whole set.

Let’s get back to making your brain stronger.

Day 11: 57. Insert Interval

You have a sorted list of non-overlapping intervals, each defined by a start and end point. Now, you're given a new interval. Your task is to insert this new interval into the existing list while keeping it sorted.

Let's set an example…

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]

Output: [[1,5],[6,9]]

Let’s gather our information first.

The array is sorted by start time, therefore, we know everything that comes before and after the interval.

So we can add it to an auxiliary vector.

Now, what do we do with the messy middle?

We can merge the overlapping intervals by finding the min and max of the overlapping intervals. That way we can ensure that we cover all of the intervals.

Here is an example…

Final Solution

Problem: Insert Interval

    

        class Solution {
        public:
            vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
                vector<vector<int>> result;
                int i = 0;
                int n = intervals.size();

                // Add all intervals that come before the new interval
                while (i < n && intervals[i][1] < newInterval[0]) {
                    result.push_back(intervals[i]);
                    i++;
                }

                // Merge overlapping intervals
                while (i < n && intervals[i][0] <= newInterval[1]) {
                    newInterval[0] = min(newInterval[0], intervals[i][0]);
                    newInterval[1] = max(newInterval[1], intervals[i][1]);
                    i++;
                }

                // Add the merged interval
                result.push_back(newInterval);

                // Add all intervals that come after the new interval
                while (i < n) {
                    result.push_back(intervals[i]);
                    i++;
                }

                return result;
            }
        };
    

We are only going to iterate the array once…