class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> finalIntervals;
        int minStart = newInterval[0];
        int maxEnding = newInterval[1];
        for (const vector<int> &interval : intervals) {
            if (overlaps(interval, newInterval)) {
                minStart = min(minStart, interval[0]);
                maxEnding = max(maxEnding, interval[1]);
            }
            else {
                finalIntervals.push_back(interval);
            }
        }
        finalIntervals.push_back({minStart, maxEnding});
        sort(begin(finalIntervals), end(finalIntervals));
        return finalIntervals;
    }

    bool overlaps(const vector<int> &a, const vector<int> &b) {
        return (a[0] <= b[0] && b[0] <= a[1]) ||
               (b[0] <= a[0] && a[0] <= b[1]);
    }
};