区间问题汇总

1.1 区间选点

AcWing 905. 区间选点

1.2 最大不相交区间数

AcWing 908. 最大不相交区间数量
452. 用最少数量的箭引爆气球
435. 无重叠区间
646. 最长数对链

1.3 带权最大不相交区间

2008. 出租车的最大盈利

你驾驶出租车行驶在一条有 n 个地点的路上。这 n 个地点从近到远编号为 1 到 n ，你想要从 1 开到 n ，通过接乘客订单盈利。你只能沿着编号递增的方向前进，不能改变方向。
乘客信息用一个下标从 0 开始的二维数组 rides 表示，其中 rides[i] = [starti, endi, tipi] 表示第 i 位乘客需要从地点 starti 前往 endi ，愿意支付 tipi 元的小费。
每一位 你选择接单的乘客 i ，你可以 盈利 endi - starti + tipi 元。你同时 最多 只能接一个订单。
给你 n 和 rides ，请你返回在最优接单方案下，你能盈利 最多 多少元。
注意：你可以在一个地点放下一位乘客，并在同一个地点接上另一位乘客。

示例 1：
输入：n = 5, rides = [[2,5,4],[1,5,1]] 输出：7 解释：我们可以接乘客 0 的订单，获得 5 - 2 + 4 = 7 元。
示例 2：
输入：n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]] 输出：20 解释：我们可以接以下乘客的订单： - 将乘客 1 从地点 3 送往地点 10 ，获得 10 - 3 + 2 = 9 元。 - 将乘客 2 从地点 10 送往地点 12 ，获得 12 - 10 + 3 = 5 元。 - 将乘客 5 从地点 13 送往地点 18 ，获得 18 - 13 + 1 = 6 元。 我们总共获得 9 + 5 + 6 = 20 元。

提示：

• 1 <= n <= 105
• 1 <= rides.length <= 3 * 104
• rides[i].length == 3
• 1 <= starti < endi <= n
• 1 <= tipi <= 105

思路：
本质还是问最大不相交区间数，只是每段区间的权重变了，最大不相交区间数变成了找到所有不相交区间组合中的的权重和的最大值。
可以用DP的方法解决
方法1：对每段区间进行DP
将区间按右端点排序
状态表示：f[i]表示考虑前i段区间，所有可能的不相交区间的组合组成的集合
属性：最大利润
状态转移：第i段区间选或不选
若选择第i段区间，需二分找前面第一个位于该区间前的区间。
能找到这样一个区间f[i] = f[l] + rides[i][2]
否则f[i] = rides[i][2]
若不选第i段区间，f[i] = Max(f[i - 1], f[i])
时间复杂度：O(NlogN)N为区间的个数
方法2：对总区间中的每个点进行DP（前提是总区间不是很大）
需要将相同终点的区间存在一起。
状态表示：f[i]表示考虑位置i及其前面的一整段区间中所有可能的不相交区间组成的集合
属性：最大利润
状态转移：以位置i为终点的区间选或不选，如果选的话，有多个以该点结尾的区间选哪一个
f[i] = Max(f[i - 1], max(f[rides[start]] + 利润))
时间复杂度：O(N + M)其中N为区间的个数，M为总区间中点的个数。虽然是双重循环，但是每个区间只会被遍历一次。

// 方法1：
class Solution {
    public long maxTaxiEarnings(int m, int[][] rides) {
        int n = rides.length;
        for (int[] p : rides)
            p[2] += p[1] - p[0];
        Arrays.sort(rides, (o1, o2) -> (o1[1] - o2[1]));
        long[] f = new long[n];
        f[0] = rides[0][2];
        for (int i = 1; i < n; i++) {
            int start = rides[i][0];
            int l = 0, r = i;
            while (l < r) {
                int mid = l + r + 1>> 1;
                if (rides[mid][1] > start)
                    r = mid - 1;
                else
                    l = mid;
            }
            if (rides[l][1] <= start)
                f[i] = f[l] + rides[i][2];
            else
                f[i] = rides[i][2];
            f[i] = Math.max(f[i], f[i - 1]);
        }
        return f[n - 1];
    }
}

// 方法2：
class Solution {
    public long maxTaxiEarnings(int n, int[][] rides) {
        Map<Integer, List<int[]>> map = new HashMap<>();
        for (int[] p : rides) {
            p[2] += p[1] - p[0];
            map.computeIfAbsent(p[1], key -> new ArrayList<>()).add(new int[]{p[0], p[2]});
        }
        long[] f = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            f[i] = f[i - 1];
            List<int[]> cur = map.get(i);
            if (cur == null) continue;
            for (int[] p : cur) {
                f[i] = Math.max(f[i], f[p[0]] + p[1]);
            }
        }
        return f[n];
    }
}

类似题目还有：
1235. 规划兼职工作

2.1 区间分组

729. 我的日程安排表 I
思路：
方法1：暴力
查询新区间与每个旧区间是否有重叠区域，如果有，不能插入，否则可以
方法2：离散化差分数组(用TreeMap实现)
方法3：TreeMap维护每个区间，直接查询是否存在重叠区域
方法4：动态开点线段树
731. 我的日程安排表 II
思路：
方法1：离散化差分数组
方法2：动态开点线段树
732. 我的日程安排表 III
思路：
方法1：离散化差分数组
方法2：动态开点线段树

3.1 区间覆盖

方法1：贪心
方法2：DP + 双指针 或者 对待覆盖区间进行DP

4.1 区间合并

方法1：排序 + 遍历合并
方法2：差分 + 离散化 / 扫描线

5 其它

[

](https://leetcode-cn.com/problems/merge-intervals/)
[

](https://www.yuque.com/zdkk/learn/bh5ug0)