leetcode 1235

leetcode 1235

class Solution {
public:
    int jobScheduling(vector<int> &startTime, vector<int> &endTime, vector<int> &profit) {
        int n = startTime.size();
        vector<vector<int>> jobs(n);
        for (int i = 0; i < n; i++) {
            jobs[i] = {startTime[i], endTime[i], profit[i]};
        }
        sort(jobs.begin(), jobs.end(), [](const vector<int> &job1, const vector<int> &job2) -> bool {
            return job1[1] < job2[1];
        });
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++) {
            int k = upper_bound(jobs.begin(), jobs.begin() + i - 1, jobs[i - 1][0], [&](int st, const vector<int> &job) -> bool {
                return st < job[1];
            }) - jobs.begin();
            dp[i] = max(dp[i - 1], dp[k] + jobs[i - 1][2]);
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

作者：力扣官方题解

经典的数据结构转变，通过3个vector, 转换成二维的vector,

start ={1,2,3,3};
end ={3,4,5,6};
val = {50, 10, 40, 70};

1 3 50 , k = 0
2 4 10 , k = 0
3 5 40 , k = 1, 也就是 dp[1] = 50
3 6 70 , k = 1, 也就是 dp[1] = 50
所以是dp[n]== 120

upper_bound

这段代码使用了 upper_bound 函数来查找一个有序容器 jobs 中第一个大于 jobs[i - 1][0] 的元素的索引

int k = upper_bound(jobs.begin(), jobs.begin() + i - 1, jobs[i - 1][0], [&](int st, const vector<int> &job) -> bool {
    return st < job[1];
}) - jobs.begin();
1
2
3

• jobs.begin()：表示容器 jobs 的起始迭代器。
• jobs.begin() + i - 1：表示容器 jobs 的截止迭代器，即从起始位置开始的前 i - 1 个元素的迭代器。
• jobs[i - 1][0]：表示要进行比较的值，这里是 jobs 中第 i - 1 个元素的第一个元素。
• [&](int st, const vector &job) -> bool { return st < job[1]; }：是一个 lambda 函数，用于比较两个元素。它接受两个参数 st 和 job，分别表示要比较的值和容器中的元素。函数体中的比较逻辑是 st < job[1]，即判断 st 是否小于 job 的第二个元素。
• upper_bound 函数返回一个迭代器，指向容器中第一个大于 jobs[i - 1][0] 的元素。
• k：表示找到的元素的索引，通过将迭代器减去容器的起始迭代器来计算得到。

总的来说，这段代码的作用是找到容器 jobs 中第一个大于 jobs[i - 1][0] 的元素的索引，并将结果存储在变量 k 中。

在 C++ 中，upper_bound 是一个函数模板，用于查找有序容器（如数组、vector 或 map）中第一个大于某个值的元素的迭代器。

upper_bound 函数的语法如下：

template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);
1
2

参数说明：

• first 和 last：定义了要搜索的元素范围，包括 first 但不包括 last。
• val：要进行比较的值。

upper_bound 函数返回一个迭代器，指向容器中第一个大于 val 的元素。如果没有找到这样的元素，它将返回 last。

下面是一个使用 upper_bound 函数的示例：

#include 
#include 
#include 

int main() {
    std::vector<int> vec = {1, 2, 2, 3, 4, 4, 5};

    // 使用 upper_bound 查找第一个大于 3 的元素
    std::vector<int>::iterator it = std::upper_bound(vec.begin(), vec.end(), 3);

    if (it != vec.end()) {
        std::cout << "First element greater than 3: " << *it << std::endl;
    } else {
        std::cout << "No element greater than 3 found" << std::endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

输出结果为：

First element greater than 3: 4
1

在这个示例中，upper_bound 函数返回一个迭代器，指向 vec 中第一个大于 3 的元素。我们可以通过解引用迭代器来获取该元素的值。

请注意，要使用 upper_bound 函数，容器中的元素必须是有序的。如果容器中的元素没有按照升序排列，则结果将是未定义的。