/*

  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
 */

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

class Solution {
public:
    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";
    }
    
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;

        sort(intervals.begin(), intervals.end(),
             [](vector<int>& a, vector<int>& b)
             {
                 return a.at(0) < b.at(0);
             }
            );        

        print("sort", intervals);
        
        return result;
    }
};

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

    for (auto tc: testCases)
    {
        Solution s;
        vector<vector<int>> input = get<0>(tc);
        vector<vector<int>> result = s.merge(input);
        s.print("input", input);        

        cout << "--------------------\n";        
    }

    return 0;
}