/*
  LeetCode 56. Merge Intervals

  Intervals are unsorted.

  Leet Code 57. Insert Interval has an sorted array of input intervals

  Given an array of intervals where intervals[i] = [starti, endi],
  merge all overlapping intervals, and return an array of the
  *non-overlapping* intervals that cover all the intervals in the input.

Example 1:

  Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
  Output: [[1,6],[8,10],[15,18]]
  Explanation: Since intervals [1,3] and [2,6] overlap, merge them
  into [1,6].

Constraints:
  1 <= intervals.length <= 104
  intervals[i].length == 2 
  0 <= starti <= endi <= 104

2. Clarifying Questions (You should ask these in the interview)
     * Can intervals be empty? (Yes, return empty vector)
     * Are intervals guaranteed to be sorted? (No)
     * Can start == end? (Yes, single point intervals)
     * Do we consider touching intervals as overlapping? e.g.
         [1,2] and [2,3] → should merge to [1,3]? (Yes, because 2 <= 2)
     * Should we modify the input in-place or return a new vector?
         (Return new one; input can be modified if convenient)

3. Brute Force Approach (O(n²) – mention but don't code deeply)
     * For each interval, check against all others for overlap.
     * Merge when max(start) <= min(end).
     * Very inefficient for n=10^4 → TLE expected.
     * We discard this quickly and move to optimal.

4. Optimal Approach (Greedy + Sorting) – O(n log n)
   Key Insight:
   Sort all intervals by start time. Then do a single linear pass, merging only with the last merged interval.

   Steps:   
   1. If intervals is empty, return {}.
   2. Sort intervals by starting point (ascending). If starts equal, sort by end doesn't matter much.
   3. Initialize a result vector with the first interval.
   4.For each subsequent interval:
      * If it overlaps with the last merged interval (curr_start <= last_end), update last_end = max(last_end, curr_end).
      * Else, append the current interval as a new merged one.
   5. Return the result.

This is greedy because once we decide not to merge, all futureintervals cannot overlap with previous
merged ones (due to sorting). Clarification

  * After we sort the intervals by their start time, the intervals are now in non-decreasing order ofstart.
  * Now, suppose at some point during the linear pass, the current interval does not overlap with
      the last merged interval in our result. That means: 
         current.start > last_merged.end

  * Because the array is sorted by start time, every remaining interval in the input (from current+1
      to the end) has a start time that is ≥ current.start.
  
Therefore:
  * future.start ≥ current.start > last_merged.end  
  * This means no future interval can ever overlap with any previously merged interval that we have
     already finalized in the result.  
  * Once we decide "this interval doesn't overlap with the last one", we can safely commit
     (finalize) that last merged interval forever — we will never need to go back and merge anything
     into it later.
  
That’s why we can greedily append it to the result and move forward. We only ever need to look at
the most recently merged interval, not the entire result list."

Time Complexity: O(n log n) dominated by sorting + O(n) pass → overall O(n log n)

Space Complexity: O(n) for the output (plus O(log n) for sort in practice, or O(1) extra if we sort in-place and reuse).

 */

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

using namespace std;

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

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;

        print("intervals", intervals);
        
        if (intervals.size() == 0) return result;
        if (intervals.size() == 1) { result.push_back(intervals.front()); return result; }

        // sort intervals vec then single liner pass over sorted vector
        sort(intervals.begin(), intervals.end());

        // push first interval into result
        result.push_back(intervals[0]);

        int begin = 0, end = 1;
        for (size_t i = 1; i < intervals.size(); i++)
        {                                                  //              back  interval[i]   merged
            if (result.back()[end] >= intervals[i][begin]) // merge, e.g. [1,3]  [2,6]        -> [1,6]
            {
                print("index: " + to_string(i) + "\n  merge ", result.back(), intervals[i]);
                result.back() = {result.back()[begin], intervals[i][end]};
            }
            else // no merge
            {
                print("index: " + to_string(i) + "\n  no merge ", result.back(), intervals[i]);
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};

struct Solution_xAI
{
    std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {
        if (intervals.empty()) {
            return {};
        }
        
        // Step 1: Sort by start time (O(n log n))
        std::sort(intervals.begin(), intervals.end());
        
        // Step 2: Initialize result with first interval
        std::vector<std::vector<int>> result;
        result.push_back(intervals[0]);
        
        // Step 3: Linear merge pass
        for (size_t i = 1; i < intervals.size(); ++i) {
            std::vector<int>& last = result.back();
            const std::vector<int>& curr = intervals[i];
            
            if (curr[0] <= last[1]) {
                // Overlap or touching → merge
                last[1] = std::max(last[1], curr[1]);
            } else {
                // No overlap → start new interval
                result.push_back(curr);
            }
        }
        
        return result;
    }    
};

int main(void)
{
    vector<tuple<vector<vector<int>>,vector<vector<int>>>> testCases = {            
        //  0      1       2        3
        { {{2,6}, {1,3}, {8,10}, {15,18}},
          {{1,6}, {8,10}, {15,18}} },

        { {{1,4}, {4,5}},
          {{1,5}} },         
        
        { {{1,4}, {4,7}},
          {{1,7}} },
        
        { {{1,2}},
          {{1,2}} },

        { {{1,2}, {3,4}},
          {{1,2}, {3,4}} },
        
        { {{1,2}, {3,4}, {5,6}},
          {{1,2}, {3,4}, {5,6}} },

        { {{1,3}, {3,4}, {4,5}, {5,6}},
          {{1,6}} },

        { {{1,3}, {3,4}, {4,5}, {6,7}},
          {{1,5},{6,7}} },
    };

    for (auto tc: testCases)
    {
        Solution s;
        vector<vector<int>> input = get<0>(tc);
        vector<vector<int>> expected = get<1>(tc);        

        vector<vector<int>> result = s.merge(input);
        print("input", input);
        print("expected", expected);
        print("result", result);
        EXPECT_EQ(expected, result);        
        cout << "--------------------\n";        
    }

    return 0;
}

void print(const string& label, vector<vector<int>>& v)
{
    cout << label <<": [";
    for (size_t i = 0; i < v.size(); i++)
    {
        cout << "[";
        for (size_t j = 0; j < v.at(i).size(); j++)
        {
            cout << v.at(i).at(j) << (j == 0 ? "," : "");
        }
        cout << (i == v.size() - 1 ? "]" : "],");
    }
    cout << "]\n";
}

void print(const string& label, vector<int>& first, vector<int>& second)
{
    string s(label + " [");
    for (auto& i: first) s += to_string(i) + ",";
    s += "], [";
    for (auto& i: second) s += to_string(i) + ",";
    s += "]";
    cout << s << endl;
}    

void print(const string& label, vector<int>& v)
{
    string s(label + " [");
    for (auto& i: v) s += to_string(i) + ",";
    s += "] ";
    cout << s << endl;
}