[leetcode/lintcode 題解] 算法面試真題詳解：最大線段覆寫

描述

在一個數軸上給出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