1751. 最多可以参加的会议数目 II #

问题描述#

给你一个 events 数组，其中 events[i] = [startDay_i, endDay_i, value_i] ，表示第 i 个会议在 startDay_i天开始，第 endDay_i 天结束，如果你参加这个会议，你能得到价值 value_i 。同时给你一个整数 k 表示你能参加的最多会议数目。

你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须完整地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。

请你返回能得到的会议价值 最大和 。

示例 1：
输入：events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
输出：7
解释：选择绿色的活动会议 0 和 1，得到总价值和为 4 + 3 = 7 。
示例 2：
输入：events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
输出：10
解释：参加会议 2 ，得到价值和为 10 。
你没法再参加别的会议了，因为跟会议 2 有重叠。你 不 需要参加满 k 个会议。
示例 3：
输入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
输出：9
解释：尽管会议互不重叠，你只能参加 3 个会议，所以选择价值最大的 3 个会议。
提示：

1 <= k <= events.length

1 <= k * events.length <= 10⁶

1 <= startDay_i <= endDay_i <= 10⁹

1 <= value_i <= 10⁶

解题思路#

动态规划加最大堆。

用 \(\texttt{dp}[k][i]\) 表示选择参加了第 \(i\) 个会议且最多参加了 \(k\) 个会议的最大价值之和。

所以 \(\texttt{dp}[k][i]\) 等于第 \(i\) 会议的价值加上在第 \(i\) 个会议之前结束的最大价值。

Python

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        n = len(events)
        events.sort()
        dp = [x[2] for x in events]
        q = [[-x, i] for i, x in enumerate(dp)]
        heapify(q)

        for _ in range(k - 1):
            for i in range(n - 1, -1, -1):
                while q and events[q[0][1]][1] >= events[i][0]:
                    heappop(q)
                if q:
                    dp[i] = events[i][2] + dp[q[0][1]]
            for i in range(n):
                heappush(q, [-dp[i], i])

        return max(dp)

C++

class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        int n = events.size();
        vector<int> dp(n);
        auto cmp = [&dp] (int i, int j) { return dp[i] < dp[j]; };
        priority_queue<int, vector<int>, decltype(cmp)> q(cmp);

        sort(events.begin(), events.end(), [] (auto &a, auto &b) { return a[0] < b[0]; });

        for (int i = 0; i < n; ++i) {
            dp[i] = events[i][2];
            q.emplace(i);
        }

        for (int i = 1; i < k; ++i) {
            for (int j = n - 1; ~j; --j) {
                while (!q.empty() && events[q.top()][1] >= events[j][0]) q.pop();
                if (!q.empty()) dp[j] = dp[q.top()] + events[j][2];
            }
            for (int j = 0; j < n; ++j) q.emplace(j);
        }

        return *max_element(dp.begin(), dp.end());
    }
};

1751. 最多可以参加的会议数目 II#

问题描述#

解题思路#

1751. 最多可以参加的会议数目 II #