<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:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        """
        ok so we can sort the array by starting times
         [[1,2],[2,3],[3,4],[1,3]] >>  [[1,2],[1,3],[2,3],[3,4]]
         >> [1,2],[1,3] one of these needs to go at least, so let's look at the next starting time
         and remove the one that doesn't overlap with it.
         >> in theory, if we had one big interval that would overlap with all, we can remove it
        """
        if not intervals:
            return 0

        # Sort intervals by their end time. If two intervals have the same ending time, they are naturally sorted in increasing order of their starting times due to the properties of the sorting algorithm.
        intervals.sort(key=lambda x: x[1])

        # Initialize the count of intervals to remove
        count_to_remove = 0
        # Set the end of the previous interval
        prev_end = intervals[0][1]

        # Iterate over the intervals starting from the second interval
        for i in range(1, len(intervals)):
            # Check if there is an overlap
            if intervals[i][0] < prev_end:
                # Overlapping interval, increment the count to remove
                count_to_remove += 1
            else:
                # No overlap, update the end time to current interval's end
                prev_end = intervals[i][1]

        return count_to_remove

55400