77 lines
2.6 KiB
Markdown
77 lines
2.6 KiB
Markdown
|
- Leetcode - Non-overlapping Intervals
|
||
|
|
id:: 643d27e0-7330-4510-a2f7-8e2cecc08e7b
|
||
|
|
- Times:
|
||
|
|
- Time when completed: 10:33
|
||
|
|
- Time taken to complete: 30mins incl. learning
|
||
|
|
- DONE Revisions:
|
||
|
|
SCHEDULED: <2023-04-23 Sun>
|
||
|
|
:LOGBOOK:
|
||
|
|
CLOCK: [2023-04-16 Sun 10:33:49]--[2023-04-16 Sun 10:33:50] => 00:00:01
|
||
|
|
CLOCK: [2023-04-23 Sun 11:00:32]--[2023-04-23 Sun 11:09:38] => 00:09:06
|
||
|
|
:END:
|
||
|
|
- Tags:
|
||
|
|
- Algorithms: #greedy
|
||
|
|
- Data structures: #array #interval
|
||
|
|
- Difficulty: #difficulty_easy
|
||
|
|
- Platforms: #leetcode
|
||
|
|
- Links:
|
||
|
|
- [link to the problem](https://leetcode.com/problems/non-overlapping-intervals/description/)
|
||
|
|
- [Previous solution](logseq://graph/logseq_notes?page=Leetcode%20Non-Overlapping-Intervals)
|
||
|
|
- Problem:
|
||
|
|
- 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_.
|
||
|
|
- Examples:
|
||
|
|
- ```
|
||
|
|
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`
|
||
|
|
- Thoughts:
|
||
|
|
- Intuition:
|
||
|
|
- This is a classic [[Interval Scheduling]] problem implemented using greedy algorithm.
|
||
|
|
- Approach:
|
||
|
|
- Sort the array by the end of interval
|
||
|
|
- Use greedy algorithm, find the interval with earliest finishing time
|
||
|
|
- Remove a interval if the starting time is before the finishing time
|
||
|
|
- otherwise, add the count
|
||
|
|
- return `length - count` for the intervals to be deleted
|
||
|
|
- Solution:
|
||
|
|
- Code
|
||
|
|
- ```java
|
||
|
|
class Solution {
|
||
|
|
public int eraseOverlapIntervals(int[][] intervals) {
|
||
|
|
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
|
||
|
|
|
||
|
|
// Interval scheduling problem
|
||
|
|
int count = 1, minEnd = intervals[0][1];
|
||
|
|
// The first can be scheduled
|
||
|
|
for (int i = 1; i < intervals.length; i++) {
|
||
|
|
if (minEnd <= intervals[i][0]) {
|
||
|
|
// can be scheduled;
|
||
|
|
count++;
|
||
|
|
minEnd = intervals[i][1];
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return intervals.length - count;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
```
|