上周五考试没有过,其中专业级第二题是关于区间的问题,在leetcode上找到类似的题目,总结复习下。

引子

先看这道题,1109. 航班预订统计,题目是这样的

这里有n 个航班,它们分别从 1 到 n 进行编号。

我们这儿有一份航班预订表,表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i j 的每个航班上预订了 k 个座位。

请你返回一个长度为 n 的数组 answer,按航班编号顺序返回每个航班上预订的座位数。参考示例如下,

输入:bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出:[10,55,45,25,25]

解题思路

将这道题的示例画一张表格表示一下,就是下面的结果

booking 1 2 3 4 5
1 10 10 0 0 0
2 0 20 20 0 0
3 0 25 25 25 25
total 10 55 45 25 25

常规思路就是以航班号为基本坐标,计算每一个航班增加的座位数,然后逐项汇总相加即可。

  1. 设置初始结果vector<int> res(n, 0);
  2. 遍历bookings,每次取其中的航班的预定数,添加到res对应的数组中,比如第1个booking,那么res[0]+=10; res[1]+=10,依次类推,直到遍历截止。

上面的算法比较简单直观,但是可以分析发现,算法的复杂度有点高,两层遍历算法时间复杂度是$O(n^2)$,空间复杂度是$O(n)$不甚理想。

有没有复杂度更简单的思路呢?这里有一个类比公交站的思路,可以将航班号码比作公交站牌,比如1号公交站,2号公交站,假定这些公交站是依次按顺序分布在一条直线公路上,i个航班的飞机的预定数目就是公交车在第i个公交站发车时候的乘客数目(包括了上车和下车的乘客数)。

举例说明,第1行表示,第1站交车上人数是10,说明公交车行驶到第1站时上车10人,到第2站时候车上的乘客仍然是10人,说明没有乘客上下车,到第3站时候车上乘客0人,说明此时有10人下车。如果使用长度为N的数组count表示每一站上下乘客的变化量(count[i] 表示第i + 1站上下车的乘客变化量),

对于booking = [i,j,k]

  1. 表示在公交站第i站上车k人,count[i - 1] += k
  2. i + 1站直到第j站都没有乘客上下车,count[i],...,count[j - 1]无操作;
  3. 在第j + 1站下车k人,所以count[j] -= k

为了方便起见,我们缩小问题的规模,以具体的数字代替抽象的代数字母,假如我们就只有3个公交站,取示例中的前2行,

  1. 公交车刚开始上的人数是0,vector<int> count(4, 0)
  2. 读取第1行,到达第1站,公交车上10人,说明上车10人,无人下车,count[0]+= 10,到达第2站公交车上依然是10人,说明也无人上车和下车,到达第3站,公交车上0人,说明10人下车,count[2] -= 10
  3. 读取第2行,公交车到达第2站,公交车上20人,说明上车20人无人下车,count[1] += 20,第3站车上20人,说明无人下车,第4站车上0人,说明有20人下车, count[3]-=20

遍历结束,得到count = {10, 20, -10,-20},那么最后每个站点的乘客数就很清楚了,到达第1站前车上乘客0人,到达后上车10人,所以第1站发车前车上10人,第2站到站后上车20人,所以第2站发车前车上乘客10 + 20 = 30人,第3站到站后下车10人,所以发车前车上乘客 30 - 10 = 20人。意思搞清楚之后,代码就很好写了。

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> res(n, 0);
        vector<int> counter(n + 1, 0);
        for (auto &booking : bookings)
        {
            int start = booking[0];
            int end = booking[1];
			// 记录每个booking的开始和结尾即可,中间的站点人数无变化
            counter[start - 1] += booking[2]; // start站上车
            counter[end] -= booking[2]; // end + 1站下车
        }
        res[0] = counter[0];
        for (int i = 1; i < n; i++)
        {
            res[i] = res[i - 1] + counter[i];
        }
        return res;
    }

时间复杂度为$O(n)$。

通用框架

「待补充」

典型题目

「待补充」

No. 986 区间列表交集

题目的链接参考986. 区间列表的交集 - 力扣(LeetCode)

No. 452 引爆气球

题目链接参考452. 用最少数量的箭引爆气球 - 力扣(LeetCode),这道题目使用贪心法,将气球的坐标放在坐标轴上,然后从0开始从左到右逐气球扫描,查看是否有交集,图示如下。

参考资料

「待补充」