解题思路

• 本题是“带容量约束的加权区间调度”问题： 既要保证所选项目在时间上两两不重叠（若一个在时间 X 结束，可接 X 开始的项目），又要满足总工作量不超过 maxEffort，并使收益最大。

• 做法：

  1. 将项目按结束时间从小到大排序，记排序后第 i 个项目为 (s[i], e[i], w[i], v[i])，分别是开始/结束/工作量/收益。

  2. 预处理每个项目 i 的“前驱” pre[i]：排序后在 i 之前、且 end <= s[i] 的最后一个项目下标（不存在则为 -1）。可用二分在结束时间数组上找到。

  3. 二维动态规划（DP）： 设 dp[i][E] 表示只考虑前 i 个项目、总可用工作量为 E 时的最大收益。转移：

     • 不选第 i 个：dp[i][E] = dp[i-1][E]
     • 选第 i 个（若 w[i] ≤ E）： dp[i][E] = max(dp[i][E], dp[pre[i]+1][E - w[i]] + v[i]) 注意这里用到的是“前驱项目集合”的最优解。

  4. 答案为 dp[n][maxEffort]。

• 相关算法：加权区间调度 + 0/1 背包（二维 DP + 二分预处理）。

复杂度分析

• 预处理排序与二分：O(n log n)
• DP 转移：O(n * maxEffort)（n ≤ 2000, maxEffort ≤ 1000，可行）
• 空间复杂度：O(n * maxEffort) （Python 采用紧凑存储以避免大内存消耗）

代码实现

Python

# -*- coding: utf-8 -*-
# 说明：输入为 5 行，依次为 startTime、endTime、effort、profit、maxEffort（以空格分隔）。
# 为稳妥与简洁，此处直接按空格 split 读取；题面保证数据合法。

import sys
from bisect import bisect_right
from array import array  # 紧凑整数数组，降低内存

def max_profit_with_effort(start, end, effort, profit, maxEffort):
    n = len(start)
    if n == 0 or maxEffort == 0:
        return 0

    # 1) 按结束时间排序
    jobs = sorted(zip(start, end, effort, profit), key=lambda x: x[1])
    s = [x[0] for x in jobs]
    e = [x[1] for x in jobs]
    w = [x[2] for x in jobs]
    v = [x[3] for x in jobs]

    # 2) 预处理前驱 pre[i]：满足 e[pre] <= s[i] 的最大下标
    pre = []
    for i in range(n):
        j = bisect_right(e, s[i]) - 1  # 最右 <= s[i]
        pre.append(j)

    # 3) 二维 DP，使用一维扁平数组紧凑存储：索引 (i, E) -> i*(maxEffort+1)+E
    M = maxEffort + 1
    dp = array('q', [0] * ((n + 1) * M))  # 'q' 为有符号 64 位整数

    for i in range(1, n + 1):
        base = i * M
        prev_base = (i - 1) * M

        # 不选第 i 个
        for E in range(M):
            dp[base + E] = dp[prev_base + E]

        # 选第 i 个（注意数组下标与 i-1 对应）
        wi = w[i - 1]
        vi = v[i - 1]
        pi = pre[i - 1] + 1  # 转为 dp 的“行号”
        pi_base = pi * M

        if wi <= maxEffort:
            for E in range(wi, M):
                cand = dp[pi_base + (E - wi)] + vi
                if cand > dp[base + E]:
                    dp[base + E] = cand

    return dp[n * M + maxEffort]

def read_ints(line):
    line = line.strip()
    if not line:
        return []
    return list(map(int, line.split()))

def main():
    data = sys.stdin.read().strip().splitlines()
    # 兼容空行：只取前 5 条有效行
    lines = []
    for t in data:
        if lines.__len__() < 5:
            lines.append(t)

    start = read_ints(lines[0]) if len(lines) > 0 else []
    end = read_ints(lines[1]) if len(lines) > 1 else []
    effort = read_ints(lines[2]) if len(lines) > 2 else []
    profit = read_ints(lines[3]) if len(lines) > 3 else []
    maxEffort = int(lines[4].strip()) if len(lines) > 4 and lines[4].strip() else 0

    ans = max_profit_with_effort(start, end, effort, profit, maxEffort)
    print(ans)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {

    // 统一：解析为 long[]，再按需转 int
    static long[] parseLongArray(String line) {
        if (line == null) return new long[0];
        line = line.trim();
        if (line.isEmpty()) return new long[0];
        String[] parts = line.split("\\s+");
        long[] arr = new long[parts.length];
        for (int i = 0; i < parts.length; i++) arr[i] = Long.parseLong(parts[i]);
        return arr;
    }

    static long solve(long[] start, long[] end, int[] effort, long[] profit, int maxEffort) {
        int n = start.length;
        if (n == 0 || maxEffort == 0) return 0L;

        // 1) 按结束时间排序
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, Comparator.comparingLong(i -> end[i]));

        long[] s = new long[n], e = new long[n], v = new long[n];
        int[] w = new int[n];
        for (int i = 0; i < n; i++) {
            int id = idx[i];
            s[i] = start[id]; e[i] = end[id]; w[i] = effort[id]; v[i] = profit[id];
        }

        // 2) 前驱
        long[] ends = e.clone();
        int[] pre = new int[n];
        for (int i = 0; i < n; i++) {
            int pos = upperBound(ends, s[i]) - 1;
            pre[i] = pos;
        }

        // 3) 二维 DP
        long[][] dp = new long[n + 1][maxEffort + 1];
        for (int i = 1; i <= n; i++) {
            for (int E = 0; E <= maxEffort; E++) dp[i][E] = dp[i - 1][E]; // 不选
            int wi = w[i - 1];
            long vi = v[i - 1];
            int pi = pre[i - 1] + 1;
            if (wi <= maxEffort) {
                for (int E = wi; E <= maxEffort; E++) {
                    dp[i][E] = Math.max(dp[i][E], dp[pi][E - wi] + vi);
                }
            }
        }
        return dp[n][maxEffort];
    }

    static int upperBound(long[] a, long key) {
        int l = 0, r = a.length;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (a[m] <= key) l = m + 1;
            else r = m;
        }
        return l;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String l1 = br.readLine();
        String l2 = br.readLine();
        String l3 = br.readLine();
        String l4 = br.readLine();
        String l5 = br.readLine();

        long[] start = parseLongArray(l1);
        long[] end   = parseLongArray(l2);
        long[] effortL = parseLongArray(l3);
        long[] profit = parseLongArray(l4);

        // 将 effort 转为 int（题面范围安全）
        int[] effort = new int[effortL.length];
        for (int i = 0; i < effortL.length; i++) effort[i] = (int)effortL[i];

        int maxEffort = 0;
        if (l5 != null && !l5.trim().isEmpty()) {
            maxEffort = (int)Long.parseLong(l5.trim());
        }

        long ans = solve(start, end, effort, profit, maxEffort);
        System.out.println(ans);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

/* 统一解析为 long long，再按需转成 int */
static vector<long long> parseLLLine(const string &line) {
    vector<long long> a;
    if (line.empty()) return a;
    stringstream ss(line);
    long long x;
    while (ss >> x) a.push_back(x);
    return a;
}

long long solve(const vector<long long>& start,
                const vector<long long>& endt,
                const vector<int>& effort,
                const vector<long long>& profit,
                int maxEffort) {
    int n = (int)start.size();
    if (n == 0 || maxEffort == 0) return 0LL;

    // 1) 按结束时间排序
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b){
        return endt[a] < endt[b];
    });

    vector<long long> s(n), e(n), v(n);
    vector<int> w(n);
    for (int i = 0; i < n; ++i) {
        int id = idx[i];
        s[i] = start[id]; e[i] = endt[id]; w[i] = effort[id]; v[i] = profit[id];
    }

    // 2) 预处理前驱 pre[i]
    vector<int> pre(n);
    for (int i = 0; i < n; ++i) {
        int pos = upper_bound(e.begin(), e.end(), s[i]) - e.begin() - 1; // 最右 <= s[i]
        pre[i] = pos; // 可能为 -1
    }

    // 3) 二维 DP
    vector<vector<long long>> dp(n + 1, vector<long long>(maxEffort + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int E = 0; E <= maxEffort; ++E) dp[i][E] = dp[i - 1][E]; // 不选
        int wi = w[i - 1];
        long long vi = v[i - 1];
        int pi = pre[i - 1] + 1;
        if (wi <= maxEffort) {
            for (int E = wi; E <= maxEffort; ++E) {
                dp[i][E] = max(dp[i][E], dp[pi][E - wi] + vi);
            }
        }
    }
    return dp[n][maxEffort];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string l1, l2, l3, l4, l5;
    getline(cin, l1);
    getline(cin, l2);
    getline(cin, l3);
    getline(cin, l4);
    getline(cin, l5);

    vector<long long> startLL  = parseLLLine(l1);
    vector<long long> endLL    = parseLLLine(l2);
    vector<long long> effortLL = parseLLLine(l3);
    vector<long long> profitLL = parseLLLine(l4);

    // 将 effort 转为 int（题面范围安全）
    vector<int> effort(effortLL.size());
    for (size_t i = 0; i < effortLL.size(); ++i) effort[i] = (int)effortLL[i];

    // 解析 maxEffort
    int maxEffort = 0;
    if (!l5.empty()) {
        stringstream ss(l5);
        long long tmp; ss >> tmp;
        maxEffort = (int)tmp;
    }

    cout << solve(startLL, endLL, effort, profitLL, maxEffort) << "\n";
    return 0;
}

题目内容

一个项目经理需要对项目进行计划制定，现有 $n$ 个项目，每个项目有一个开始时间 $startTime[i]$、结束时间 $endTime[i]$ 以及所需投入的人力 $effort[i]$ ，完成每个项目能获得的收益为 $profit[i]$ 。

项目团队可以投入的最大工作量为 $maxEffort$ ，并且在时间上重叠的项目不能同时开展。

如果一个项目在时间 $X$ 结束，可以立刻承接在时间 $X$ 开始的新项目。

请编写一个函数，计算在不超过可以投入最大工作量为 $maxEffort$ 的情况下，合理安排计划获得的最大收益。

输入描述

函数包含 $5$ 个参数，前四个数组参数，长度相同且 $≤ 2000$，数值均 $≤10^9$ ，$5$ 个参数分 $5$ 行输入，数组数据以 "$,$" 分割，示例如下:

1、开始时间数组 $startTime,0≤$ 数组长度及数据 $≤2000$ ，示例: $1$ $5$ $9$ ;

2、结束时间数组 $endTime，0≤$ 数组长度及数据 $≤2000$ ，示例: $3$ $7$ $11$ ;

3、所需投入的工作量 $effort，0≤$ 数组长度及数据 $≤2000$ ，示例:$20$ $30$ $10$ ;

4、以及获得收益数组 $profit$ ，$0≤$ 数组长度及数据 $≤2000$ ，示例:$20$ $80$ $30$ ;

5、可以投入最大工作量 $maxEffort，0 ≤ maxEffort ≤1000$ ，示例:$40$

输入完整示例如下:

$1,5,9$

$3,7,11$

$20,30,10$

$20,80,30$

$40$

输出描述

在不超过每日工作量上限的情况下，安排合理计划获得最大收益

样例1

输入

2 4 7
6 8 11
20 20 20
30 90 30
40

输出

90

说明

选择第二个项目，由于时间与其他项目时间重叠

无法选取其他项目，总精力为 $20<=40$ ,总收益为 $90$

样例2

输入

1 5 9
3 7 11
20 30 10
20 80 30
40

输出

110

说明 选择第二个和第三个项目，总精力为 $30+10=40<=40$ ,总收益为 $80+30=110$