差分数组

以本周的练习题引入

本周数据结构继续学习数组，主要讲了什么数组的压缩存储，也就是对特殊矩阵(对称矩阵)以及稀疏矩阵怎样减少区间消耗的问题。不过不太好用OJ考察，所以做的题目仍然是对数组的简单处理，第三题有点意思，可以做一些延伸。题目如图。

problem3

容易想到，讲师的数目的限制来自于课程重叠。也就是说，如果我们求出课程的最大重叠，也就是讲师的最小数目。观察数据范围，由于时间被限制在0~24了，我们可以对每个时刻，统计正在上的课，最大值就是答案。

需要注意的是，题目认为老师可以立即去上下一节课，也就是说：0~1,1~2这样的情况，只需要1名老师即可。所以，我们可以认为，上课的时间是[begin,end)，一个左闭右开区间，所以，我们维护一个长为24的数组(0~23)，对每一节课，把[begin,end)中的时间++，然后返回最大值即可。最坏时间复杂度O(24*N)。代码如下：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> vec(24);
    int n, beg, end;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> beg >> end;
        for (int j = beg; j < end; ++j)
            ++vec[j];
    }
    cout << *max_element(vec.begin(), vec.end()) << endl;
    return 0;
}

对上述算法的反思

需要指出，上述方法限制很大，因为我们已经知道，时间是以0~24小时来表示，这才能创建那个定长数组，然而，如果我们对时间不做限制，怎么办呢？一种朴素的想法，是找到输入的最大值，以它为长度建立数组。它的缺点是：一来，我们可能要不断改变数组的长度，这会麻烦而且耗时；二来，即使我们知道了最大值，如果它很大(比如说1e9)，由于最坏时间复杂度是O(max*n)，这是不可接受的。

怎么能优化这个算法呢？需要使用差分数组的技巧。

差分数组

考虑一个子问题：当我们知道了T1时正在上的课的数目，怎样去求T2时正在上的课的数目？显然，我们只要加上从(T1,T2]开始上的课，再减去(T1,T2]之间结束的课，就行了。也就是说，有这样的公式：T2-T1==beg-end(注意，每个量都是课的数目)，这，就是对正在上的课程数做了差分，(差分，就是作差使数分开)。

依照这个思路，如果我们保存各个节点开始的课-结束的课的数目，再从头到尾不断求和，就得到了各个时间段正在上的课的数目。

例如，对于这样的输入：1 3;3 6;2 7，我们可以得到这样的差分数组0 1 1 0 0 0 -1 -1(0~7)，然后求前缀和，就得到：0 1 2 2 2 2 1 0，其中的最大值就是最大重叠。

换言之，对差分数组求前缀和就是答案数组。各个节点开始的课-结束的课的数目形成的数组，就是差分数组。

这种方法的时间复杂度又如何呢？由于我们只处理输入的开头和结尾，而不管中间的时刻，形成差分数组的过程是O(2N)的，然而，求前缀和以及答案数组的最大值的时间复杂度是O(max)的(不过比之前的O(max*n)要好多了)，也并没有解决数组变长的问题。还需要进一步优化。

再看一遍差分数组，发现其中有好多的0，显然，0并不会影响前缀和的结果，所以，对于我们寻找答案数组的最大值的过程，0是无意义的。而0是怎么产生的呢？要么是此时上课下课相抵，而更多的情况是：并没有在输入中出现。可以想见，没有在输入中出现的时刻，在差分数组中一定是0，所以可以舍去，我们只要保存出现的数就好了。比较好的思路，是利用字典。

维护一个map，每次++map[beg],--map[end]，得到的就是压缩后的差分数组。比如上面的例子：1 3;3 6;2 7，得到的差分数组是1-1,2-1,3-0,6-(-1),7-(-1)，只有五个节点(是出现过的所有开头结尾，一定<=2N)。这样的压缩思路，将储存、求前缀和、求最大值的时空复杂度，都压到了O(2N)，算法总的时空复杂度就是O(2N)。比上面的要好太多了(尤其是在max很大时)。

依据这种思路写出的代码如下(其实也不比上面麻烦，但是大大优化了)：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    map<int, int> memo;
    int beg, end, n, ans = 0, now = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i)//用map构建差分数组
    {
        cin >> beg >> end;
        ++memo[beg], --memo[end];
    }
    for (auto &p : memo)//求前缀和
    {
        now += p.second;
        ans = max(ans, now);
    }
    cout << ans << endl;
    return 0;
}