Insert_Interval

class Solution {
public:
    static bool compare (vector<int> &v1, vector<int> &v2) {
        //cout <<"HA";
        if (v1[0] == v2[0]) {
            return v1[1] < v2[1];
        }
        return v1[0] < v2[0];
    }
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        vector<vector<int>> ans;
        //edge cases
        if (n == 0) {
            ans.push_back({newInterval[0],newInterval[1]});
            return ans;
        }
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (intervals[i][1] >= newInterval[0] and intervals[i][0] <= newInterval[1]) {
                intervals[i][0] = min(intervals[i][0], newInterval[0]);
                intervals[i][1] = max(intervals[i][1], newInterval[1]);
                cnt++;
            }
        }
        //edge cases
        if (cnt == 0) {
            intervals.push_back({newInterval[0], newInterval[1]});
            sort(intervals.begin(), intervals.end(), compare);
            return intervals;
        }

        sort(intervals.begin(), intervals.end(), compare);

        int index = 0;

        for (int i = 1; i < n; ++i) {
            if (intervals[index][1] >= intervals[i][0]) {
                intervals[index][0] = min(intervals[index][0], intervals[i][0]);
                intervals[index][1] = max(intervals[index][1], intervals[i][1]);
            }
            else {
                index++;
                intervals[index] = intervals[i];
            }
        }



        for (int i = 0; i <= index; ++i) {
            ans.push_back({intervals[i][0],intervals[i][1] });
        }

        return ans;
    }
};