/*
  Leet Code 435. Non-overlapping Intervals
  
  Medium

  Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum
  number of intervals you need to remove to make the rest of the intervals non-overlapping.

  Note that intervals which only touch at a point are non-overlapping.
     For example, [1, 2] and [2,3] are non-overlapping.

  Example 1:

  Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
  Output: 1
  Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
  Example 2:

  Input: intervals = [[1,2],[1,2],[1,2]]
  Output: 2
  Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.
  Example 3:

  Input: intervals = [[1,2],[2,3]]
  Output: 0
  Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
 

  Constraints:

  1 <= intervals.length <= 105
  intervals[i].length == 2
  -5 * 104 <= starti < endi <= 5 * 104

  * Key Insight (Greedy Algorithm)

  The problem is equivalent to: Find the maximum number of non-overlapping intervals you can keep,
  then removals = total - max_non_overlapping.
  
  To maximize the number kept:
    * Sort the intervals by their ending time (ascending).
    * Greedily pick the interval that ends earliest — this leaves the most room for future intervals.
 
  Then iterate
    * if the next interval starts after or at the current end, keep it and update the end;
    * else, it overlaps → count as removal.

  This is a classic greedy on intervals (similar to Activity Selection Problem).

  Why Sort by End Time? (Discussion Question)
    * Sorting by start time can lead to suboptimal choices (you might pick a long interval that
        blocks many short ones).  
    * Ending earliest is optimal because it maximizes future options.
    * Proof intuition: Suppose you have two overlapping candidates; always better to keep the one
        that finishes first.

  Time & Space Complexity
    * Time: O(n log n) — dominated by sorting. Traversal is O(n).
    * Space: O(1) extra (ignoring input) or O(log n) if sort is in-place with extra space for
         comparator. In practice, very efficient for n=1e^5.  
*/

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

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

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals, vector<vector<int>>& resultVector)
    {
        if (intervals.empty()) return 0;

        // 1. First sort intervals by ending time ascending
        sort(intervals.begin(), intervals.end(),
             [](const vector<int>& a, const vector<int>& b)
             { int end = 1; return a[end] < b[end];});
        
        print("sorted", intervals);

        int begin = 0, end = 1;        
        int removals = 0;
        vector<int> current = intervals[0];
        resultVector.push_back(intervals[0]);

        // sorted: [[1,2],[2,3],[1,3],[3,4]]
        
        // 2. Iterate
        for (size_t i = 1; i < intervals.size(); i++)
        {
            if (current[end] <= intervals[i][begin])
            {
                current = intervals[i];
                resultVector.push_back(intervals[i]);
            }            
            else
                removals++;
        }
 
        return removals;
    }
};

int main(void)
{
    vector<tuple<vector<vector<int>>, int, vector<vector<int>>>> testCases = {
        // // input                    removed resultVec
        { {{1,2},{2,3},{3,4},{1,3}}, 1,      {{1,2},{2,3},{3,4}} },
        { {{1,2},{1,2},{1,2}},       2,      {{1,2}}             },
        { {{1,2},{2,3}},             0,      {{1,2},{2,3}}       },
        { {{1,2}},                   0,      {{1,2}}             },
      //{ {{}},                      0,      {{}}                },
    };

    vector<vector<int>> v;    
    tuple<vector<vector<int>>, int, vector<vector<int>>> t = make_tuple(v,0,v);
    testCases.push_back(t);
        
    Solution s;
    
    for (const auto& tc: testCases)
    {
        vector<vector<int>> input = get<0>(tc);
        int expectedRemoved = get<1>(tc);
        vector<vector<int>> expectedResultVector = get<2>(tc);
        vector<vector<int>> resultVector;
        int removed = s.eraseOverlapIntervals(input, resultVector);
        EXPECT_EQ(removed, expectedRemoved);
        EXPECT_EQ(resultVector, expectedResultVector);

        print("        input", input);
        print(" resultVector", resultVector);        
        cout << "----------------------------------------\n";
    }
}

void print(const string& tag, vector<vector<int>>& intervals)
{
    if (intervals.empty()) { cout << tag << ": []" << endl; return; }

    string s = tag + ": [";    
    for (auto i: intervals)
    {
        s += "[";
        for (auto j: i)
            s += to_string(j) + ",";
        s = s.substr(0, s.size()-1);
        s += "],";
    }
    s = s.substr(0, s.size()-1);
    s += "]";
    cout << s << endl;
}