ช่วงที่ไม่ทับซ้อน (Non-overlapping Intervals)
ให้ชุดของช่วง (intervals) หาจำนวนช่วงน้อยที่สุดที่ต้องลบเพื่อให้ช่วงที่เหลือไม่ทับซ้อนกัน
ตัวอย่าง: [[1,2],[2,3],[3,4],[1,3]] → ลบ [1,3] 1 ช่วง เหลือ [1,2],[2,3],[3,4] ที่ไม่ทับซ้อน
ขั้นตอนการแก้ปัญหา (Greedy: Interval Scheduling)
- ถ้าอาร์เรย์ว่าง คืนค่า 0
- เรียงช่วงตาม end time จากน้อยไปมาก
end = arr[0][1],count = 1- วน
i = 1ถึงn-1:- ถ้า
arr[i][0] >= end:end = arr[i][1],count++
- ถ้า
- คืนค่า
n - count(จำนวนที่ต้องลบ)
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
return a[1] < b[1];
});
int cnt = 1, end = intervals[0][1];
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] >= end) {
end = intervals[i][1];
cnt++;
}
}
return intervals.size() - cnt;
}
};
อินพุทและเอาต์พุทตัวอย่าง
Input: [[1,2],[1,2],[1,2]]
Output: 2
