-
Notifications
You must be signed in to change notification settings - Fork 1
/
435.无重叠区间.go
94 lines (91 loc) · 1.69 KB
/
435.无重叠区间.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import "sort"
/*
* @lc app=leetcode.cn id=435 lang=golang
*
* [435] 无重叠区间
*
* https://leetcode-cn.com/problems/non-overlapping-intervals/description/
*
* algorithms
* Medium (40.76%)
* Likes: 47
* Dislikes: 0
* Total Accepted: 2.4K
* Total Submissions: 5.8K
* Testcase Example: '[[1,2]]'
*
* 给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。
*
* 注意:
*
*
* 可以认为区间的终点总是大于它的起点。
* 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。
*
*
* 示例 1:
*
*
* 输入: [ [1,2], [2,3], [3,4], [1,3] ]
*
* 输出: 1
*
* 解释: 移除 [1,3] 后,剩下的区间没有重叠。
*
*
* 示例 2:
*
*
* 输入: [ [1,2], [1,2], [1,2] ]
*
* 输出: 2
*
* 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
*
*
* 示例 3:
*
*
* 输入: [ [1,2], [2,3] ]
*
* 输出: 0
*
* 解释: 你不需要移除任何区间,因为它们已经是无重叠的了。
*
*
*/
func eraseOverlapIntervals(intervals [][]int) int {
n := len(intervals)
if n <= 0 {
return 0
}
sort.Slice(intervals, func(i, j int) bool {
if intervals[i][0] < intervals[j][0] {
return true
} else if intervals[i][0] > intervals[j][0] {
return false
} else {
return intervals[i][1] < intervals[j][1]
}
})
dp := make([]int, n)
dp[0] = 1
maxPair := 1
for i := 1; i < n; i++ {
for j := i - 1; j >= 0; j-- {
if intervals[i][0] >= intervals[j][1] {
dp[i] = max(dp[i], dp[j]+1)
} else {
dp[i] = max(dp[i], 1)
}
}
maxPair = max(maxPair, dp[i])
}
return n - maxPair
}
func max(a, b int) int {
if a > b {
return a
}
return b
}