You are given an array of intervals where each interval has a start and end value. Your task is:

Remove the minimum number of intervals so that the remaining intervals do not overlap.

Return the minimum number of intervals that must be removed.

Example:

Input:  [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: Removing [1,3] lets others coexist.

Another example:

Input:  [[1,2],[1,2],[1,2]]
Output: 2

---

Problem Understanding

Two intervals overlap if:

next.start < previous.end

We want the maximum number of intervals that can stay without overlapping, so that removals are minimized.

If we determine how many intervals can remain without overlapping, then:

minimum removals = total intervals − non-overlapping intervals

---

Logic Explained in Simple English

The key idea:

To keep as many intervals as possible, always keep the one that ends first.

Why?

• An interval that ends earlier leaves more room for upcoming intervals
• This is a classic greedy scheduling principle
• Sorting by end time ensures maximum future compatibility

So the plan:

1. Sort intervals by end value
2. Keep track of the end of the last chosen interval
3. Walk through intervals:
   • If current interval does NOT overlap → keep it and update lastEnd
   • If it overlaps → we skip it (meaning we would remove it)
4. Count how many we skip → that’s the answer

This way we avoid overlap while removing the fewest intervals.

---

Step-by-Step Approach

1. If intervals list is empty, return 0
2. Sort intervals by ascending end time
3. Set count = 0 (number removed)
4. Track prevEnd = intervals[0].end
5. Loop through remaining intervals:
   • If interval.start < prevEnd → overlap → increment count
   • Else → update prevEnd to interval.end
6. Return count

---

Java Implementation

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        
        int removals = 0;
        int prevEnd = intervals[0][1];
        
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < prevEnd) {
                removals++;
            } else {
                prevEnd = intervals[i][1];
            }
        }
        
        return removals;
    }
}

---

Dry Run Example

Input:

[[1,2],[2,3],[3,4],[1,3]]

Step 1 — Sort by end time

Sorted:

[1,2], [1,3], [2,3], [3,4]

Step 2 — Process intervals

Start:

prevEnd = 2
removals = 0

Check [1,3]:

1 < 2 → overlaps → removals = 1
(prevEnd unchanged)

Check [2,3]:

2 < 2 → NO overlap → prevEnd = 3

Check [3,4]:

3 < 3 → NO overlap → prevEnd = 4

Final result:

removals = 1

Output:

1

---

Time and Space Complexity

Time Complexity

O(n log n)

Due to sorting — traversal is linear.

Space Complexity

O(1)

Sorting done in place.

---

Common Mistakes and How to Avoid Them

Mistake 1: Sorting by start time

Sorting by start time does NOT guarantee minimal removals.

Mistake 2: Removing longest interval instead of earliest-ending

Greedy must prioritize shortest end.

Mistake 3: Misidentifying overlap

Overlap rule:

current.start < prev.end

Mistake 4: Trying dynamic programming

DP works but is unnecessary and slower.

Mistake 5: Thinking touching intervals overlap

Intervals such as [1,2] and [2,3] do not overlap.