Hard

题目描述

给你一个二维整数数组 intervals，其中 intervals[i] = [li, ri, weighti]。区间 i 从位置 li 开始，在 ri 结束，权重为 weighti。你可以选择最多 4 个非重叠区间。所选区间的得分定义为它们权重的总和。

返回具有最大得分的最多 4 个区间索引的字典序最小数组，表示你选择的非重叠区间。

如果两个区间不共享任何点，则称为非重叠。特别地，共享左边界或右边界的区间被认为是重叠的。

示例 1:

输入: intervals = [[1,3,2],[4,5,2],[1,5,5],[6,9,3],[6,7,1],[8,9,1]]
输出: [2,3]
解释: 你可以选择索引为 2 和 3 的区间，权重分别为 5 和 3。

示例 2:

输入: intervals = [[5,8,1],[6,7,7],[4,7,3],[9,10,6],[7,8,2],[11,14,3],[3,5,5]]
输出: [1,3,5,6]
解释: 你可以选择索引为 1、3、5 和 6 的区间，权重分别为 7、6、3 和 5。

约束条件:

  • 1 <= intervals.length <= 5 * 10^4
  • intervals[i].length == 3
  • intervals[i] = [li, ri, weighti]
  • 1 <= li <= ri <= 10^9
  • 1 <= weighti <= 10^9

解题思路

这是一个经典的区间调度优化问题，结合了动态规划和贪心策略。

核心思路：

  1. 排序策略：按照区间的右端点进行排序，这样可以保证在处理当前区间时，所有可能的前置区间都已经被考虑过了
  2. 状态设计：使用 dp[k][i] 表示从前 i 个区间中选择最多 k 个非重叠区间的最大权重
  3. 状态转移：对于每个区间，有两种选择：
    • 不选择当前区间：dp[k][i] = dp[k][i-1]
    • 选择当前区间：需要找到最近的不重叠区间，使用二分查找优化

算法步骤：

  1. 为每个区间添加原始索引，然后按右端点排序
  2. 使用动态规划计算最大权重，同时记录选择路径
  3. 通过回溯找到具体的区间选择方案
  4. 为了保证字典序最小，在权重相同时优先选择索引较小的方案

时间优化： 使用二分查找来快速定位最近的非重叠前置区间，将朴素的 O(n²) 优化为 O(n log n)。

代码实现

class Solution {
public:
    vector<int> maximumWeight(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<tuple<int, int, int, int>> sortedIntervals;
        
        for (int i = 0; i < n; i++) {
            sortedIntervals.push_back({intervals[i][1], intervals[i][0], intervals[i][2], i});
        }
        sort(sortedIntervals.begin(), sortedIntervals.end());
        
        vector<vector<long long>> dp(5, vector<long long>(n + 1, 0));
        vector<vector<int>> parent(5, vector<int>(n + 1, -1));
        
        for (int i = 1; i <= n; i++) {
            auto [r, l, w, idx] = sortedIntervals[i - 1];
            
            for (int k = 1; k <= 4; k++) {
                dp[k][i] = dp[k][i - 1];
                parent[k][i] = parent[k][i - 1];
                
                int lastNonOverlap = -1;
                int left = 0, right = i - 1;
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (get<0>(sortedIntervals[mid]) < l) {
                        lastNonOverlap = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                
                long long newScore = w + (lastNonOverlap >= 0 ? dp[k - 1][lastNonOverlap + 1] : 0);
                if (newScore > dp[k][i]) {
                    dp[k][i] = newScore;
                    parent[k][i] = lastNonOverlap + 1;
                }
            }
        }
        
        long long maxScore = 0;
        int bestK = 0, bestI = 0;
        for (int k = 1; k <= 4; k++) {
            for (int i = 1; i <= n; i++) {
                if (dp[k][i] > maxScore) {
                    maxScore = dp[k][i];
                    bestK = k;
                    bestI = i;
                }
            }
        }
        
        vector<int> result;
        int curK = bestK, curI = bestI;
        while (curK > 0 && curI > 0) {
            int prevI = parent[curK][curI];
            if (prevI != parent[curK][curI - 1]) {
                result.push_back(get<3>(sortedIntervals[curI - 1]));
                curK--;
                curI = prevI;
            } else {
                curI--;
            }
        }
        
        sort(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def maximumWeight(self, intervals: List[List[int]]) -> List[int]:
        n = len(intervals)
        sorted_intervals = []
        
        for i in range(n):
            sorted_intervals.append((intervals[i][1], intervals[i][0], intervals[i][2], i))
        sorted_intervals.sort()
        
        dp = [[0] * (n + 1) for _ in range(5)]
        parent = [[-1] * (n + 1) for _ in range(5)]
        
        for i in range(1, n + 1):
            r, l, w, idx = sorted_intervals[i - 1]
            
            for k in range(1, 5):
                dp[k][i] = dp[k][i - 1]
                parent[k][i] = parent[k][i - 1]
                
                last_non_overlap = -1
                left, right = 0, i - 1
                while left <= right:
                    mid = (left + right) // 2
                    if sorted_intervals[mid][0] < l:
                        last_non_overlap = mid
                        left = mid + 1
                    else:
                        right = mid - 1
                
                new_score = w + (dp[k - 1][last_non_overlap + 1] if last_non_overlap >= 0 else 0)
                if new_score > dp[k][i]:
                    dp[k][i] = new_score
                    parent[k][i] = last_non_overlap + 1
        
        max_score = 0
        best_k, best_i = 0, 0
        for k in range(1, 5):
            for i in range(1, n + 1):
                if dp[k][i] > max_score:
                    max_score = dp[k][i]
                    best_k, best_i = k, i
        
        result = []
        cur_k, cur_i = best_k, best_i
        while cur_k > 0 and cur_i > 0:
            prev_i = parent[cur_k][cur_i]
            if prev_i != parent[cur_k][cur_i - 1]:
                result.append(sorted_intervals[cur_i - 1][3])
                cur_k -= 1
                cur_i = prev_i
            else:
                cur_i -= 1
        
        result.sort()
        return result

public class Solution {
    public int[] MaximumWeight(IList<IList<int>> intervals) {
        int n = intervals.Count;
        var sortedIntervals = new List<(int r, int l, int w, int idx)>();
        
        for (int i = 0; i < n; i++) {
            sortedIntervals.Add((intervals[i][1], intervals[i][0], intervals[i][2], i));
        }
        sortedIntervals.Sort();
        
        var dp = new long[5][];
        var parent = new int[5][];
        for (int i = 0; i < 5; i++) {
            dp[i] = new long[n + 1];
            parent[i] = new int[n + 1];
            Array.Fill(parent[i], -1);
        }
        
        for (int i = 1; i <= n; i++) {
            var (r, l, w, idx) = sortedIntervals[i - 1];
            
            for (int k = 1; k <= 4; k++) {
                dp[k][i] = dp[k][i - 1];
                parent[k][i] = parent[k][i - 1];
                
                int lastNonOverlap = -1;
                int left = 0, right = i - 1;
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (sortedIntervals[mid].r < l) {
                        lastNonOverlap = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                
                long newScore = w + (lastNonOverlap >= 0 ? dp[k - 1][lastNonOverlap + 1] : 0);
                if (newScore > dp[k][i]) {
                    dp[k][i] = newScore;
                    parent[k][i] = lastNonOverlap + 1;
                }
            }
        }
        
        long maxScore = 0;
        int bestK = 0, bestI = 0;
        for (int k = 1; k <= 4; k++) {
            for (int i = 1; i <= n; i++) {
                if (dp[k][i] > maxScore) {
                    maxScore = dp[k][i];
                    bestK = k;
                    bestI = i;
                }
            }
        }
        
        var result = new List<int>();
        int curK = bestK, curI = bestI;
        while (curK > 0 && curI > 0) {
            int prevI = parent[curK][curI];
            if (prevI != parent[curK][curI - 1]) {
                result.Add(sortedIntervals[curI - 1].idx);
                curK--;
                curI = prevI;
            } else {
                curI--;
            }
        }
        
        result.Sort();
        return result.ToArray();
    }
}

var maximumWeight = function(intervals) {
    const n = intervals.length;
    const sortedIntervals = [];
    
    for (let i = 0; i < n; i++) {
        sortedIntervals.push([intervals[i][1], intervals[i][0], intervals[i][2], i]);
    }
    sortedIntervals.sort((a, b) => a[0] - b[0]);
    
    const dp = Array(5).fill().map(() => Array(n + 1).fill(0));
    const parent = Array(5).fill().map(() => Array(n + 1).fill(-1));
    
    for (let i = 1; i <= n; i++) {
        const [r, l, w, idx] = sortedIntervals[i - 1];
        
        for (let k = 1; k <= 4; k++) {
            dp[k][i] = dp[k][i - 1];
            parent[k][i] = parent[k][i - 1];
            
            let lastNonOverlap = -1;
            let left = 0, right = i - 1;
            while (left <= right) {
                const mid = Math.floor((left + right) / 2);
                if (sortedIntervals[mid][0] < l) {
                    lastNonOverlap = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            
            const newScore = w + (lastNonOverlap >= 0 ? dp[k - 1][lastNonOverlap + 1] : 0);
            if (newScore > dp[k][i]) {
                dp[k][i] = newScore;
                parent[k][i] = lastNonOverlap + 1;
            }
        }
    }
    
    let maxScore = 0;
    let bestK = 0, bestI = 0;
    for (let k = 1; k <= 4; k++) {
        for (let i = 1; i <= n; i++) {
            if (dp[k][i] > maxScore) {
                maxScore = dp[k][i];
                bestK = k;
                bestI = i;
            }
        }
    }
    
    const result = [];
    let curK = bestK, curI = bestI;
    while (curK > 0 && curI > 0) {
        const prevI = parent[curK][curI];
        if (prevI !== parent[curK][curI - 1]) {
            result.push(sortedIntervals[curI - 1][3]);
            curK--;
            curI = prevI;
        } else {
            curI--;
        }
    }
    
    result.sort((a, b) => a - b);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(n log n)排序需要 O(n log n)，动态规划过程中每个状态需要二分查找 O(log n)
空间复杂度O(n)需要 O(n) 的 dp 数组和 parent 数组存储状态信息

相关题目