[每日一题] 1235.规划兼职工作

Richard

2024 年 05 月 04 日

95 次浏览

暂无评论

1559字数

LeetCode

> https://leetcode.cn/problems/maximum-profit-in-job-scheduling/description/?envType=daily-question&envId=2024-05-02

明显该题具有最优子结构，最优工作序列除去一个后也是最优解，因此考虑使用 DP 求解。

我们可以对工作按照结束时间排序。对于第 $i$ 个工作，我们可以选择做或者不做，那么就对应以下两种情况：

- 选择做第 $i$ 个工作。由于工作时间不能重叠，所以需要找到一个最大的 $j$ ，使得 $endTime[j] \leq StartTime[i]$ 。此时最大报酬就为前 $j$ 个工作的最大利润加上 $profit[i]$ 。
- 选择不做第 $i$ 个工作。此时最大报酬为前 $i - 1$ 个工作的最大报酬。

此时状态转移方程就出来了：
$$
dp[i] = max(dp[i - 1], dp[j] + profit[i])
$$
其中 $dp[i]$ 表示前 $i$ 个工作能获取的最大报酬，$j$ 表示满足 $endTime[j] \leq StartTime[i]$ 的最大值。

代码实现中因为结束时间有序，所以可以使用二分查找计算出 $j$ 。

```c++
class Solution {
public:
    int jobScheduling(std::vector<int> &startTime, std::vector<int> &endTime, std::vector<int> &profit) {
        const int n = startTime.size();

std::vector<int> idx(n);
        std::iota(idx.begin(), idx.end(), 0);
        std::sort(idx.begin(), idx.end(), [&](const int &i, const int &j) {
            return endTime[i] < endTime[j];
        });

int former;
        std::vector<int> dp(n + 1);
        for (int i = 0; i < n; ++i) {
            former = std::upper_bound(idx.begin(), idx.begin() + i, startTime[idx[i]],
                                      [&](const int &value, const int &element) { return value < endTime[element]; }) -
                     idx.begin();
            dp[i + 1] = std::max(dp[i], profit[idx[i]] + dp[former]);
        }

return dp[n];
    }
};
```

- 时间复杂度：$O(nlogn)$ 。排序所需的时间复杂度为 $O(nlogn)$ ；每次二分查找都需要 $O(logn)$ 的时间，总共查找了 $n$ 次，所以查找的时间复杂度也为 $O(nlogn)$ ；所以总的时间复杂度为 $O(nlogn)$ 。
- 空间复杂度：$O(n)$ 。

最后修改：2024 年 05 月 04 日