区间

区间问题通常需要考虑排序, 按左还是右排序很关键
考虑 2 个区间的场景:

相交
包含
不相交

合并区间

56. 合并区间 mid

以数组 intervals 表示若干个区间的集合, 其中单个区间为 intervals[i] = [starti, endi]. 请你合并所有重叠的区间, 并返回一个不重叠的区间数组, 该数组需恰好覆盖输入中的所有区间.

有点是否可触达的感觉, 按左端点排序, 先划定一个区间(第一个区间的范围)
遍历所有区间, 如果有重叠就更新右端点, 没有就将前一个区间加入

java

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> list = new ArrayList<>();
        int l = intervals[0][0], r = intervals[0][1];
        for (int[] e : intervals) {
            // 新区间
            if (r < e[0]) {
                list.add(new int[]{l, r});
                l = e[0];
                r = e[1];
            }
            // 融合
            else r = Math.max(r, e[1]);
        }
        //最后的区间没加
        list.add(new int[]{l, r});

        int[][] res = new int[list.size()][];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

区间重叠高度

253. 会议室 II mid

给你一个会议时间安排的数组 intervals, 每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi], 返回所需会议室的最小数量.

解法贪心

先按左端点整体排序, 确定入堆顺序; 然后优先队列中放入右端点, 相当于合并

java

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int[] e : intervals) {
            if (!heap.isEmpty() && heap.element() <= e[0]) heap.remove();
            heap.add(e[1]);
        }
        return heap.size();
    }
}

2406. 将区间分为最少组数 mid

给你一个二维整数数组 $i n t e r v a l s$ , 其中 $i n t e r v a l s [i] = [l e f t_{i}, r i g h t_{i}]$ 表示闭区间 $[l e f t_{i}, r i g h t_{i}]$ .

你需要将 $i n t e r v a l s$ 划分为一个或者多个区间组, 每个区间只属于一个组, 且同一个组中任意两个区间不相交.

请你返回最少需要划分成多少个组.

如果两个区间覆盖的范围有重叠(即至少有一个公共数字), 那么我们称这两个区间是相交的. 比方说区间 $[1, 5]$ 和 $[5, 8]$ 相交.

解法 1 贪心

先按左端点整体排序, 确定入堆顺序; 然后优先队列中放入右端点, 相当于合并

java

class Solution {
    public int minGroups(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int[] e : intervals) {
            if (!heap.isEmpty() && heap.element() < e[0]) heap.remove();
            heap.add(e[1]);
        }
        return heap.size();
    }
}

解法 2 排队上车

start 上车, end 下车, 求车上最多的人
差分数组, [s,e]+=1

java

class Solution {
    public int minGroups(int[][] intervals) {
        int min = Integer.MAX_VALUE, max = 0;
        for (int[] pair : intervals) {
            min = Math.min(min, pair[0]);
            max = Math.max(max, pair[1]);
        }
        int[] diff = new int[max - min + 2];
        for (int[] pair : intervals) {
            diff[pair[0] - min]++;
            diff[pair[1] - min + 1]--;
        }
        int res = 1, sum = 0;
        for (int val : diff) {
            sum += val;
            res = Math.max(res, sum);
        }
        return res;
    }
}

不重叠区间

435. 无重叠区间 mid

给定一个区间的集合 intervals, 其中 intervals[i] = [starti, endi]. 返回需要移除区间的最小数量, 使剩余区间互不重叠.

区间 [1,2] 和 [2,3] 的边界相互“接触”, 但没有相互重叠.

解法贪心

如果 2 个区间重叠, 只能选 1 个. 先开始的不一定先结束, 所以按右端点自然排序, 尽可能早结束
如果左端点小于上一个右端点, 计数

java

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[1]));
        Integer lastEnd = null;
        int cnt = 0;
        for (int[] e : intervals) {
            if (lastEnd == null || lastEnd <= e[0]) lastEnd = e[1];
            else cnt++;
        }
        return cnt;
    }
}

452. 用最少数量的箭引爆气球 mid

有一些球形气球贴在一堵用 XY 平面表示的墙面上. 墙面上的气球记录在整数数组 points, 其中 $p o i n t s [i] = [x_{s} t a r t, x_{e} n d]$ 表示水平直径在 $x_{s} t a r t$ 和 $x_{e} n d$ 之间的气球. 你不知道气球的确切 y 坐标.

一支弓箭可以沿着 x 轴从不同点完全垂直地射出. 在坐标 x 处射出一支箭, 若有一个气球的直径的开始和结束坐标为 $x_{s} t a r t$ , $x_{e} n d$ , 且满足 $x_{s} t a r t \leq x \leq x_{e} n d$ , 则该气球会被引爆. 可以射出的弓箭的数量没有限制. 弓箭一旦被射出之后, 可以无限地前进.

给你一个数组 points, 返回引爆所有气球所必须射出的最小弓箭数.

解法

考虑 3 种(相交不相交包含)场景, 按右端点排序, 从右端点射入

Java

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, Comparator.comparingInt(o -> o[1]));
        int cnt = 0;
        Integer lastEnd = null;
        for (int[] e : points) {
            if (lastEnd == null || lastEnd < e[0]) {
                cnt++;
                lastEnd = e[1];
            }
        }
        return cnt;
    }
}

646. 最长数对链 mid

给出 n 个数对。在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d)才可以跟在(a, b)后面。我们用这种形式来构造一个数对链。

给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

解法 1 贪心

最多不重叠区间的数量

java

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, Comparator.comparingInt(o -> o[1]));
        int cnt = 0;
        Integer lastEnd = null;
        for (int[] e : pairs) {
            if (lastEnd == null || lastEnd < e[0]) {
                cnt++;
                lastEnd = e[1];
            }
        }
        return cnt;
    }
}

解法 2 DP

DP 和贪心都可以解, DP 复杂度 $O (n^{2})$ , 贪心复杂度 $O (n)$
第 i 个区间为结尾的对数
$f_{i} = m a x (f_{j}) j \in [0, n - 1], b < c$

java

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, Comparator.comparingInt(a -> a[0]));
        int[] dp = new int[pairs.length];
        dp[0] = 1;
        int max = dp[0];
        for (int i = 1; i < pairs.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (pairs[j][1] < pairs[i][0]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

在线不重叠区间

729. 我的日程安排表 I

LCR 058. 我的日程安排表 I

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成重复预订，则可以存储这个新的日程安排。
当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生重复预订。
日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为，start <= x < end.

实现 MyCalendar 类：

MyCalendar() 初始化日历对象。
boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

解法 TreeMap

用 start 还是 end 当 key 是一样的
[l,r) [s,e) 相交情况：
s >= l && s < r
s <= l && e > l
也可以从另一个角度思考，比 e 小的最大 l 所对应的 r 要小于 s

java

class MyCalendar {
    private final TreeMap<Integer, Integer> map = new TreeMap<>();

    public boolean book(int start, int end) {
        Map.Entry<Integer, Integer> entry = map.floorEntry(end - 1);
        if (entry != null && entry.getValue() > start) return false;
        map.put(start, end);
        return true;
    }
}

解法 Set

定义 compare

java

class MyCalendar {
    private final TreeSet<int[]> set = new TreeSet<>((a, b) -> {
        if (a[0] >= b[1]) return 1;
        if (a[1] <= b[0]) return -1;
        return 0;
    });

    public boolean book(int start, int end) {
        return set.add(new int[]{start, end});
    }
}

还有线段树解法

区间 ​

合并区间 ​

56. 合并区间 mid ​

区间重叠高度 ​

253. 会议室 II mid ​

2406. 将区间分为最少组数 mid ​

不重叠区间 ​

435. 无重叠区间 mid ​

452. 用最少数量的箭引爆气球 mid ​

646. 最长数对链 mid ​

在线不重叠区间 ​

729. 我的日程安排表 I ​

区间

合并区间

56. 合并区间 mid

区间重叠高度

253. 会议室 II mid

2406. 将区间分为最少组数 mid

不重叠区间

435. 无重叠区间 mid

452. 用最少数量的箭引爆气球 mid

646. 最长数对链 mid

在线不重叠区间

729. 我的日程安排表 I