/*
  LeetCode 57. Insert Interval

  Input intervals are sorted.

  LeetCode 56. Merge Intervals has an unsorted arrray of input intervals
  
  You are given an array of non-overlapping intervals intervals where intervals[i] =
  [start_i, end_i] 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.

  Constraints:
    * 0 <= intervals.length <= 104
    * intervals[i].length == 2
    * 0 <= starti <= endi <= 105
    * intervals is sorted by starti in ascending order.
    * newInterval.length == 2
    * 0 <= start <= end <= 105
    
  Optimal Approach – Greedy One-Pass (O(n) time)
  Because intervals are sorted and non-overlapping, we can do three clear phases in a single pass:

  1. Add all non-overlapping intervals that end before newInterval starts
      (intervals[i][1] < newInterval[0])
  2. Merge all overlapping intervals into newInterval itself
      * While current interval overlaps:
      * newInterval[0] = min(newInterval[0], intervals[i][0])
      * newInterval[1] = max(newInterval[1], intervals[i][1])
  3. Add the (possibly merged) newInterval, then add all remaining intervals.


  This is O(n) time and O(n) space (for the result vector).
  Why it's optimal: We traverse the list only once. No sorting needed. 
*/

#include <bits/stdc++.h>
#include <gtest/gtest.h>
 
using namespace std;

void print(vector<vector<int>>&, const string&);
void print(vector<int>&, const string&);

class Solution_old //: public testing::Test
{
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& 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;
    }
};

class Solution
{
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval)
    {
        if (intervals.size() == 0) return vector<vector<int>> {{newInterval}};

        vector<vector<int>> result;

        // 1. find start interval for merge
        int i = 0;
        int begin = 0, end = 1;

        //example: { {{1,2},{3,5},{6,7},{8,10},{12,16}}, {4,8}, {{1,2},{3,10},{12,16}}},

        // find start of merge
        while (i < (int) intervals.size() && newInterval[begin] > intervals[i][end])
        {
            result.push_back(intervals[i]);
            i++;
        }
        // {1,2}

        // 2. merge {4,8}
        while (i < (int)intervals.size() && newInterval[end] >= intervals[i][begin])
        {
            newInterval[begin] = min(newInterval[begin], intervals[i][begin]);
            newInterval[end] = max(newInterval[end], intervals[i][end]);
            cout << format("newInterval: {},{}\n", newInterval[begin], newInterval[end]);
            i++;
            // {3,5}  -> {3,8}
            // {6,7}  -> {3,8}
            // {8,10} -> {3,10}
        }

        result.push_back(newInterval);

        // 3. push back any remaining intervals
        while (i < (int)intervals.size())
        {
            result.push_back(intervals[i]);
            i++;
        }
        // {12,16}

        return result;        
    }
};
    
    
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;

    for (auto testCase: testCases)
    {
        vector<vector<int>> result = s.insert(get<0>(testCase), get<1>(testCase));
        vector<vector<int>> expected = get<2>(testCase);
        EXPECT_EQ(result, expected);
        print(get<0>(testCase), "input");        
        print(get<2>(testCase), "expected");
        print(result, "  result");
        cout << "---------------------------------------" << endl;
    }

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

    return 0;
}

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

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