## Strategy
* Sort the array. This makes it easy to compare intervals to see if two intervals overlap. Why? Because, potentially overlapping intervals will be next to each other in a sorted array. If the array is not sorted we would have to compare an interval against all the other intervals to see if they overlap.
* Given two intervals: \[start1, end1] and \[start2, end2]
* intervals overlap if: start1 <= start2 < end1
* However, since the array is sorted we do **NOT** need to do the start1 <= start2 check. The array is sorted so we are guaranteed that start1 <= start2. We just need to check that start2 < end1.
* To decide which interval to discard we keep track of the end value. Which end value is used depends on whether we are in an overlap or not.
* If start2 < end1 (in an overlap)
* end = min(end, end2)
* Here the minimum of the previous end and the 2nd end is used. Why? Because we want to find the minimum number of intervals to discard. An interval with a higher end point will span additional numbers, which means there could potentially be more intervals to come that would fall in that range. So, by eliminating that end point we are getting the minimum number of intervals to remove.
* Otherwise we are not in an overlap (start2 >= end1):
* end = end2
* Why? Because there is not an overlap, so we do not want to keep track of the previous end. It is no longer of concern. The 2nd end is used, because that value will be compared against the next interval in the list.
## Solution
```python
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort()
answer = 0
end = intervals[0][1]
for interval in intervals[1:]:
if interval[0] < end:
answer += 1
end = min(end, interval[1])
else:
end = interval[1]
return answer
```
Time complexity: O(n log n). The time complexity is from sorting the array.
Space complexity: O(1). This is because the array is sorted in place, but it means the input array is modified. If the input array is not allowed to be modified then a seperate sorted array would need to be created and the space complexity would be O(n).
## Take-away
Drawing pictures really helped in this situation.
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://monica-granbois.gitbook.io/cs-theory-and-problems/problems/leetcode/435.-non-overlapping-intervals.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.