最大化控制资源成本 - 华为OD统一考试(差分数组)

差分数组

差分其实就是数据之间的差，什么数据的差呢？就是上面所给的原始数组的相邻元素之间的差值，我们令 d[i]=a[i+1]-a[i]，一遍for循环即可将差分数组求出来。
当我们希望对原数组的某一个区间[l,r]施加一个增量inc时，差分数组d对应的变化是：d[l]增加inc，d[r+1]减少inc，并且这种操作是可以叠加的。

例如：有数组d=[1,2,3,4,5,6]，对d[2]到d[4]之间的所有数加上3，变为d=[1,2,6,7,8,6]，那么差分数组也就从[1,1,1,1,1,1]变成了[1,1,4,1,1,-2]。
当我们需要对原数组的不同区间施加不同的增量，我们只要按规则修改差分数组即可。

题目描述

公司创新实验室正在研究如何最小化资源成本，最大化资源利用率，请你设计算法帮他们解决一个任务分布问题:有taskNum项任务，每人任务有开始时间(startTime) ，结更时间(endTme) 并行度(paralelism) 三个属性，并行度是指这个任务运行时将会占用的服务器数量，一个服务器在每个时刻可以被任意任务使用但最多被一个任务占用，任务运行完成立即释放(结束时刻不占用)。任务分布问题是指给定一批任务，让这批任务由同一批服务器承载运行，请你计算完成这批任务分布最少需要多少服务器，从而最大最大化控制资源成本。

输入描述

第一行输入为taskNum，表示有taskNum项任务 接下来taskNum行，每行三个整数，表示每个任务的开始时间(startTime ) ，结束时间 (endTime ) ，并行度 (parallelism)

输出描述

一个整数，表示最少需要的服务器数量

示例

输入
3
2 3 1
6 9 2
0 5 1
输出
2

说明
共有三个任务，第一个任务在时间区间[2，3] 运行，占用1个服务器，第二个任务在时间区间[6，9] 运行，占用2个服务器，第三个任务在时间区间[0，5] 运行，占用1个服务器，需要最多服务器的时间区间为[2，3] 和[6，9] ，需要2个服务器。

#include <vector>
#include <algorithm>
#include <iostream>

#define N 50000 + 5

using namespace std;

int main() {
    int taskNum;
    cin >> taskNum;
    // 差分数组
    vector<int> d(N);

    int startTime,endTime,parallelism;
    for(int i=0; i<taskNum; i++) {
        cin >> startTime >> endTime >> parallelism;
        d[startTime] += parallelism;
        d[endTime] -= parallelism;
    }

    int result = 0;
    for(int i=0, sum = 0; i<N; i++) {
        //　sum 表示的是 i 时间，执行所有任务所需服务器数量
        sum += d[i];
        result = max(result, sum);
    }

    cout << result << endl;


    return 0;
}