$$\color{Red}{区间分组=三种语言PII版和贪心版}$$

我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小 输出最小组数。

1.算法细节

• 为什么用小根堆存放每组最大的右端点值？

我们每次存放进去一个组的最大右端点值在小根堆的作用是：当遍历到一个新的组，如果它的左端点小于最小的右端点，意味着它会在每个组右端点后面：即和他们均冲突。此时才需要开一个新组。

如果采用大根堆，如果小于最大的右端点，但是它可能和其他更小右端点的组没有冲突，因此对于是否开新组还需要逐个去比对，得不偿失。（其实本题朴素情况下，就是逐个比对，而小根堆优化了这个过程。）

• 为什么不小于的时候需要弹出最小的右端点值，并插入当前点的右端点？这是替代关系吗？

未必是替代关系，同组相当于当成一个合并的集合来看待，合并之后最小组的右端点势必发生变化，因此需要删除之前的右端点，而插入新的右端点代表更新当前这个新集合的右端点，但是是不是最小就不好说了。最深刻的是：这个小根堆存放的一个个元素代表的不仅仅是一个右端点信息，而是以右端点值排序的一个个经一段段区间而成的集合，每个集合就是一个组，我们优先能加入一个区间到一个组，即有交集的情况下，加入那个右值最小的组。

1.将所有区间按照左端点从小到大排序。
2.从前往后枚举每一个区间：
    判断这个区间能否分到某个组中去(L[i] > Max_r) (实际判断可以求所有组max_r中的min值来判断)
    ①成立：这个区间的左端点大于某个组中的区间的右端点最大值，说明没有交集，可以放进这个组，
    并更新这个组的max_r
    ②不成立：这个区间的左端点小于所有组中右端点的最大值，即都有交集，所有需新创建一个组

2.具体代码

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    static int N = 100010, n;

    static class Edge {
        int l, r;

        public Edge(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }

    static PriorityQueue<Integer> q = new PriorityQueue<>();
    static Edge[] edges = new Edge[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] s2 = br.readLine().split(" ");
            int l = Integer.parseInt(s2[0]);
            int r = Integer.parseInt(s2[1]);
            edges[i] = new Edge(l, r);
        }
        Arrays.sort(edges, 0, n, Comparator.comparingInt(o -> o.l));
        for (int i = 0; i < n; i++) {
            if (q.isEmpty() || edges[i].l <= q.peek()){
                q.add(edges[i].r);
            }else {
                q.remove();
                q.add(edges[i].r);
            }
        }
        System.out.println(q.size());
    }
}

python3

import heapq
q = []
heapq.heapify(q)
edge = []
n = int(input())
for i in range(n):
    a, b = map(int, input().split())
    edge.append((a, b))

edge.sort(key = lambda x: x[0])
for i in range(n):
    if not q or edge[i][0] <= q[0]:
        heapq.heappush(q, edge[i][1])
    else:
        heapq.heapreplace(q, edge[i][1])

print(len(q))

C++

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10;

struct Seg{
    int l, r;
}s[N];

bool cmp(Seg a, Seg b){
    return a.l < b.l;
}

int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n; i++)   scanf("%d%d", &s[i].l, &s[i].r);

    sort(s, s + n, cmp);

    priority_queue <int, vector<int>, greater<int>> heap;
    for(int i=0; i<n; i++)
    {
        if(heap.empty() || heap.top() >= s[i].l)    heap.push(s[i].r);
        else
        {
            heap.pop();
            heap.push(s[i].r);
        }
    }

    cout << heap.size() << endl;
    return 0;
}