class Solution {
public int jobScheduling(int[] st, int[] et, int[] ps) {
int n = st.length;
List<int[]> list = new ArrayList<>();
for (int i = 0; i < n; i++) list.add(new int[]{st[i], et[i], ps[i]});
Collections.sort(list, (a, b)->a[1] - b[1]);
int[] f = new int[n + 10];
for (int i = 1; i <= n; i++) {
int[] info = list.get(i - 1);
int a = info[0], b = info[1], c = info[2];
f[i] = Math.max(f[i - 1], c);
int l = 0, r = i - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (list.get(mid)[1] <= a) l = mid;
else r = mid - 1;
}
if (list.get(r)[1] <= a) f[i] = Math.max(f[i], f[r + 1] + c);
}
return f[n];
}
}
C++ 代码：
代码语言：javascript
复制
class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int n = startTime.size();
vector<vector<int>> list(n);
for (int i = 0; i < n; i++) list[i] = {startTime[i], endTime[i], profit[i]};
sort(list.begin(), list.end(), [](vector<int> a, vector<int> b)->bool{return a[1] < b[1];});
vector<int> f(n + 10, 0);
for(int i = 1; i <= n; i++) {
int a = list[i - 1][0], b = list[i - 1][1], c = list[i - 1][2];
f[i] = max(f[i - 1], c);
int l = 0, r = i - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (list[mid][1] <= a) l = mid;
else r = mid - 1;
}
if (list[r][1] <= a) f[i] = max(f[i], f[r + 1] + c);
}
return f[n];
}
};
Python 代码：
代码语言：javascript
复制
class Solution:
def jobScheduling(self, st: List[int], et: List[int], ps: List[int]) -> int:
n = len(st)
jobs = [(st[i], et[i], ps[i]) for i in range(n)]
jobs.sort(key=lambda x: x[1])
f = [0] * (n + 10)
for i in range(1, n + 1):
a, b, c = jobs[i - 1]
f[i] = max(f[i - 1], c)
l, r = 0, i - 1
while l < r:
mid = l + r + 1 >> 1
if jobs[mid][1] <= a:
l = mid
else:
r = mid - 1
if jobs[r][1] <= a:
f[i] = max(f[i], f[r + 1] + c)
return f[n]
TypeScript 代码：
代码语言：javascript
复制
function jobScheduling(st: number[], et: number[], ps: number[]): number {
const n = st.length
const list = new Array<Array<number>>()
for (let i = 0; i < n; i++) list.push([st[i], et[i], ps[i]])
list.sort((a,b)=>a[1]-b[1])
const f = new Array<number>(n + 10).fill(0)
for (let i = 1; i <= n; i++) {
const info = list[i - 1]
const a = info[0], b = info[1], c = info[2]
f[i] = Math.max(f[i - 1], c)
let l = 0, r = i - 1
while (l < r) {
const mid = l + r + 1 >> 1
if (list[mid][1] <= a) l = mid
else r = mid - 1
}
if (list[r][1] <= a) f[i] = Math.max(f[i], f[r + 1] + c)
}
return f[n]
}
