435. Non-overlapping Intervals
Tags:
Medium
Skills:
Interval
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm số lượng interval tối thiểu cần loại bỏ để các interval còn lại không bị overlap. Hai interval chỉ chạm nhau ở điểm cuối/ đầu thi không được coi là overlap (VD [1, 2] và [2, 3]
Approach
Các bước chính
end )prev_end là điểm kết thúc của interval đầu tiênstart của interval hiện tại < prev_end thì bị overlap → Tăng biến đếm số cần loại bỏprev_end = điểm kết thúc của interval hiện tạiSolution
1function eraseOverlapIntervals(intervals: number[][]): number {
2 if (intervals.length === 0) return 0;
3 intervals.sort((a, b) => a[1] - b[1])
4 let count = 0;
5 let prev_end = intervals[0][1];
6
7 for (let i = 1; i < intervals.length; i++) {
8 let [start, end] = intervals[i];
9 if (prev_end > start) {
10 count++
11 } else {
12 prev_end = end;
13 }
14 }
15
16 return count;
17
18};