<p>Given an array of intervals <code>intervals</code> where <code>intervals[i] = [start<sub>i</sub>, end<sub>i</sub>]</code>, return <em>the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> intervals = [[1,2],[1,2],[1,2]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> You need to remove two [1,2] to make the rest of the intervals non-overlapping.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> intervals = [[1,2],[2,3]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> You don&#39;t need to remove any of the intervals since they&#39;re already non-overlapping.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= intervals.length &lt;= 10<sup>5</sup></code></li>
	<li><code>intervals[i].length == 2</code></li>
	<li><code>-5 * 10<sup>4</sup> &lt;= start<sub>i</sub> &lt; end<sub>i</sub> &lt;= 5 * 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        if (intervals.empty()) return 0;
        // Sort the intervals based on end time, and then it helps to check on gap
        // between prev and curr intervals
        sort(intervals.begin(), intervals.end(), [&intervals](vector<int> a1, vector<int> a2) 
                                    { return a1[1] < a2[1]; }
            );
        // int prevEnd = INT_MIN;
        int prevEnd = intervals[0][1];
        int ans = 0;
        // for (auto interval : intervals) {
        for (int idx = 1; idx < intervals.size(); idx ++) {
            // If prevEnd is bigger than current start, its an overlap. 
            // And then update the prevEnd
            #if 0
            if (prevEnd > interval[0]) {
                ans ++;
                prevEnd = max(prevEnd, interval[1]);
            } else {
                // Move prevEnd to current one when there is no overlap
                prevEnd = interval[1];
            }
            #else
            if (intervals[idx][0] >= prevEnd) {
                // If current start is bigger than prevEnd, there is NO overlap. Update prevEnd
                prevEnd = intervals[idx][1];
            } else {
                // otehrwise, there is an overlap. Increase the counter
                // !!! Use the same prevEnd !!! DO NOT update, as current one is SKIPPED !!!
                ans ++;
            }
            #endif
        }
        return ans;
    }
};
288484