描述

在一个数轴上给出 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. 

题解

dp[i][j]dp[i][j]表示用 jj 个线段覆盖前 ii 个数的最优答案。先将所有线段按照左端点排序，对于左端点相同的线段，取最长的拿来转移。 则有：dp[i+1][j]=max(dp[i][j],dp[i+1][j])dp[i+1][j]=max(dp[i][j],dp[i+1][j]) dp[i+num][j+1]=max(dp[i][j]+num,dp[i+num][j+1])dp[i+num][j+1]=max(dp[i][j]+num,dp[i+num][j+1])(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];     } } 

更多题解参考