描述
在一个数轴上给出n个线段,问选择不超过k个线段,使得这k个线段覆盖的数最多。
在线评测地址:领扣题库官网
样例1
Input:
[(1,2),(2,3),(3,4)]
2
Output: 4
Explanation:
Select the line segment (1,2), (3,4), which can cover the 4 numbers of 1,2,3,4.
样例2
Input:
[(1,2),(2,3),(1,7)]
2
Output: 7
Explanation:
Selecting the line segment (1,7) ,which can cover the 7 numbers of 1,2,3,4,5,6,7.
题解
dpidpi表示用jj个线段覆盖前ii个数的最优答案。先将所有线段按照左端点排序,对于左端点相同的线段,取最长的拿来转移。 则有: dpi+1=max(dpi,dpi+1)dpi+1=max(dpi,dpi+1) dpi+num=max(dpi+num,dpi+num)dpi+num=max(dpi+num,dpi+num)(num为线段长度)
/**
* Definition of Interval:
* public classs Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* @param intervals: The intervals
* @param k: The k
* @return: The answer
*/
class Cmp implements Comparator<Interval>{
@Override
public int compare(Interval a, Interval b){
if(a.start == b.start) {
return a.end - b.end;
}
return a.start - b.start;
}
}
public int maximumLineCoverage(List<Interval> intervals, int k) {
// Write your code here
Collections.sort(intervals, new Cmp());
int index = 0;
int num = 0;
int maxnum = 0;
int[][] dp = new int[2005][2005];
for (int i = 0; i < intervals.size(); i++) {
maxnum = Math.max(intervals.get(i).end, maxnum);
}
for (int i = 0; i < maxnum; i++) {
while (index < intervals.size() && intervals.get(index).start == i + 1) {
num = Math.max(num, intervals.get(index).end - intervals.get(index).start + 1);
index++;
}
for (int j = 0; j <= k; j++) {
dp[i + 1][j] = Math.max(dp[i][j], dp[i + 1][j]);//不取
if (i + num <= maxnum) {
dp[i + num][j + 1] = Math.max(dp[i][j] + num, dp[i + num][j + 1]);//取
}
}
if (num > 0) {//i加了1,所以线段长度减1
num--;
}
}
return dp[maxnum][k];
}
}
更多题解参考:九章官网solution