#include <bits/stdc++.h>
#include <gtest/gtest.h>

/*
  57. Insert Interval
  
  You are given an array of non-overlapping intervals intervals where
  intervals[i] = [starti, endi] represent the start and the end of the
  ith interval and intervals is sorted in ascending order by
  starti. You are also given an interval newInterval = [start, end]
  that represents the start and end of another interval.

  Insert newInterval into intervals such that intervals is still
  sorted in ascending order by starti and intervals still does not
  have any overlapping intervals (merge overlapping intervals if
  necessary).

  Return intervals after the insertion.

  Note that you don't need to modify intervals in-place. You can make
  a new array and return it.
*/

 
using namespace std;

class Solution //: public testing::Test
{
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval)
    {
        print(intervals, "intervals");
        print(newInterval, "newInterval");

        if (intervals.size() == 0) return vector<vector<int>> {{newInterval}};
        
        int newIntervalStart = newInterval[0], newIntervalEnd = newInterval[1];

        vector<vector<int>> result;

        // find start merge interval
        size_t idx_start = 0;
        auto intervalsIter = intervals.begin();        
        for (; idx_start < intervals.size(); idx_start++, intervalsIter++)
        {
            vector<int> currInterval = intervals[idx_start];
            if ( (newIntervalStart >= currInterval[0] && newIntervalStart <= currInterval[1]) ||
                 newIntervalStart < currInterval[0] )
                break;
            else
                result.push_back(currInterval);
        }
        
        // find end merge interval
        size_t idx_end = idx_start;
        for (; idx_end < intervals.size(); idx_end++, intervalsIter++)
        {
            if (idx_end == intervals.size() - 1)
                break;

            vector<int> currInterval = intervals[idx_end];
            vector<int> nextInterval = intervals[idx_end + 1];
            if ( (newIntervalEnd > currInterval[1] && newIntervalEnd < nextInterval[0]) ||
                 newIntervalEnd <= currInterval[1])
                break;
        }

        // merge
        vector<int> startInterval, endInterval;
        
        if (idx_start == idx_end && idx_start == intervals.size())
        {
            // case where newInterval is greater than the endInterval
            startInterval = newInterval;
            endInterval = newInterval;
        }
        else if (idx_start == idx_end && intervals[idx_start][0] > newIntervalEnd)
        {
            // case where newInterval is less than currentInterval
            startInterval = newInterval;
            endInterval = newInterval;
            intervals.insert(intervalsIter,{newInterval});
        }        
        else
        {
            startInterval = intervals[idx_start];
            endInterval = intervals[idx_end];
        }
        
        cout << "merge start: " << startInterval[0] << "," << startInterval[1] << " idx_start: " << idx_start << endl;
        cout << "merge end: " << endInterval[0] << "," << endInterval[1] << " idx_end: " << idx_end << endl;
        print(result, "result");

        int startval = newIntervalStart < startInterval[0] ? newIntervalStart : startInterval[0];
        int endval = newIntervalEnd > endInterval[1] ? newIntervalEnd : endInterval[1];
        vector<int> v{startval, endval};
        result.push_back(v);

        idx_end++;
        while( idx_end < intervals.size())
            result.push_back(intervals[idx_end++]);
        
        return result;
    }

    void print(vector<vector<int>>& intervals, const char* tag)
    {
        cout << tag << ": ";
        for (auto i: intervals)
        {
            cout << "{"; for (auto j: i) cout << j << ",";
            cout << "} ";
        }
        cout << endl;
    }

    void print(vector<int>& v, const char* tag)
    {
        cout << tag << ": {";
        for (auto i: v) cout << i << ",";
        cout << "}" << endl;
    }
};


int main(int argc, char** argv)
{
    vector<tuple<vector<vector<int>>,vector<int>,vector<vector<int>>>> testCases = {
        // input                              new interval  expected output
        { {{1,3},{6,9}},                      {2,5},        {{1,5},{6,9}} },
        { {{1,2},{3,5},{6,7},{8,10},{12,16}}, {4,8},        {{1,2},{3,10},{12,16}}},
        { {{1,5},{6,10},{20,30}},             {7,11},       {{1,5},{6,11},{20,30}}},
        { {{1,2},{3,4},{5,6},{7,8},{9,10}},   {1,11},       {{1,11}}},
        { {},                                 {5,7},        {{5,7}}},
        { {{1,5}},                            {6,8},        {{1,5},{6,8}}},
        { {{1,5}},                            {0,3},        {{0,5}}},
        { {{2,3},{5,7}},                      {0,6},        {{0,7}} },
        { {{1,5}},                            {0,0},        {{0,0},{1,5}}},
        { {{3,5},{12,15}},                     {6,6},        {{3,5},{6,6},{12,15}}}
    };

    Solution s;

    [[maybe_unused]] auto printVec = [](vector<int>& v) { cout << "{"; for (auto& i: v) { cout << i; } cout << "," << endl; };
        
    for (auto testCase: testCases)
    {
        vector<vector<int>> result = s.insert(get<0>(testCase), get<1>(testCase));

        s.print(get<2>(testCase), "expected");
        s.print(result, "  result");
        cout << "---------------------------------------" << endl;
    }

    //testing::InitGoogleTest(&argc, argv);
    
    //int ret = RUN_ALL_TESTS();
    
    // return ret;
    return 0;
}