编程技巧 - 合并区间 - 《学习笔记》

一维合并区间
二维合并区间

一维合并区间

Acwing 803.区间合并	数学	区间合并

题目描述
给定 n 个区间 [li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3]和[2,6]可以合并为一个区间[1,6]。

输入格式
第一行包含整数n。
接下来n行，每行包含两个整数l和r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围
1≤n≤100000,
−109≤li≤ri≤109
样例
输入样例：

输出样例：

思路：按照每段区间的左端点排序，根据单调性遍历一遍数组找到所有能合并的区间并合并。
时间复杂度：O(nlogn)
空间复杂度 O(n)
注意：这里空间复杂度可以是O(1)，因为题目只让求合并完后的区间个数，没有讲求出所有区间的具体内容。
上代码：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] a = new int[n][2];
        for (int i = 0; i < n; i++) {
            a[i][0] = sc.nextInt();
            a[i][1] = sc.nextInt();
        }
        Arrays.sort(a, (o1, o2) -> o1[0] - o2[0]);
        int cnt = 0;
        int l = a[0][0], r = a[0][1];
        for (int i = 1; i < n; i++) {
            if (a[i][0] <= r) {
                r = Math.max(r, a[i][1]);
            } else {
                cnt++;
                l = a[i][0];
                r = a[i][1];
            }
        }
        cnt++;
        System.out.println(cnt);
    }
}

Arrays.sort(a, (o1, o2) -> o1[0] - o2[0]);
        // int cnt = 0;
        int n = a.length;
        int l = a[0][0], r = a[0][1];
        List<int[]> list = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            if (a[i][0] <= r + 1) {
                r = Math.max(r, a[i][1]);
            } else {
                // cnt++;
                list.add(new int[]{l, r});
                l = a[i][0];
                r = a[i][1];
            }
        }
        // cnt++;
        // list.add(new int[]{l, r});
        // for (int[] b : list)
        //     System.out.println(Arrays.toString(b));
        n = list.size();
        int[][] b = new int[n][2];
        for (int i = 0; i < n; i++) {
            b[i][0] = list.get(i)[0];
            b[i][1] = list.get(i)[1];
        }
        int max = 0;
        int cnt = 0;
        int left = 0;
        for (int i = 0, j = 0; j < n; j++) {
            max = Math.max(max, Math.min(c, b[j][1] - b[j][0] + 1));
            while (i < n && b[i][1] <= left + c - 1) {
                cnt += Math.min(left + c - 1, b[i][1]) - b[i][0] + 1;
                i++;
                max = Math.max(max, cnt);
            }
            // System.out.println(j + " " + max);
        }
        return max;

二维合并区间

759. 格子染色	数学	区间合并

题目描述：
在二维平面上有一个无限的网格图形，初始状态下，所有的格子都是空白的。
现在有 n 个操作，每个操作是选择一行或一列，并在这行或这列上选择两个端点网格，把以这两个网格为端点的区间内的所有网格染黑（包含这两个端点）。
问经过 n 次操作以后，共有多少个格子被染黑，重复染色同一格子只计数一次。
输入格式
第一行包含一个正整数 n。
接下来 n 行，每行包含四个整数 x1,y1,x2,y2，表示一个操作的两端格子坐标。
若 x1=x2则是在一列上染色，若 y1=y2则是在一行上染色。
保证每次操作是在一行或一列上染色。
输出格式
包含一个正整数，表示被染黑的格子的数量。
数据范围
1≤n≤10000,
−109≤x1,y1,x2,y2≤109
输入样例：

输出样例：

思路：相较于上题，问题从一维变成二维，而且还是两个二维的叠加。

读数据，行列分开
分别对行列的数据排序，按照位置，起止点的顺序进行排序
合并区间并计算区间大小（即统计被染黑的格子数量）
去重（行和列可能有重复的色块）
打印输出 ```java import java.util.*;

class Seg { int pos; int start; int end; Seg(int pos, int start, int end) { this.pos = pos; this.start = Math.min(start, end); this.end = Math.max(start, end); } } public class Main { public static void main(String[] sss) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); List rows = new ArrayList<>(); List cols = new ArrayList<>();

    for(int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        x1 = sc.nextInt();
        y1 = sc.nextInt();
        x2 = sc.nextInt();
        y2 = sc.nextInt();
        //行号相同
        if (x1 == x2) {
            rows.add(new Seg(x1, y1, y2));
        }
        //列号相同
        else {
            cols.add(new Seg(y1, x1, x2));
        }
    }
    //合并,数色块
    long ans = merge(rows) + merge(cols);
    for (int i = 0; i < rows.size(); i++) {
        Seg tmp = rows.get(i);
        System.out.println(tmp.pos + " " + tmp.start + " " + tmp.end);
    }
    for (int i = 0; i < cols.size(); i++) {
        Seg tmp = cols.get(i);
        System.out.println(tmp.pos + " " + tmp.start + " " + tmp.end);
    }
    //去掉重复色块
    for (int i = 0; i < rows.size(); i++) {
        Seg row = rows.get(i);
        for (int j = 0; j < cols.size(); j++) {
            Seg col = cols.get(j);
            if (row.start <= col.pos && row.end >= col.pos && col.start <= row.pos && col.end >= row.pos)
                ans--;
        }
    }
    System.out.println(ans);
}
static long merge(List<Seg> list) {
    List<Seg> res = new ArrayList<>();
    long sum = 0;
    list.sort((o1, o2) -> {
        if (o1.pos != o2.pos) return o1.pos - o2.pos;
        else if (o1.start != o2.start) return o1.start - o2.start;
        else return o1.end - o2.end;
    });
    int MIN = Integer.MIN_VALUE;
    for (int i = 0, j = 0; i < list.size();) {
        //递增j直至下一行/列
        while (j < list.size() && list.get(i).pos == list.get(j).pos) j++;
        int start = MIN + 1, end = MIN; 
        for (int k = i; k < j; k++) {
            Seg tmp = list.get(k);
            if (tmp.start > end) {
                sum += end - start + 1;
                if (start != MIN+1) {
                    res.add(new Seg(list.get(i).pos, start, end));
                }
                start = tmp.start;
                end = tmp.end;
            }
            else {
                end = Math.max(end, tmp.end);
            }
        }
        sum += end - start + 1;
        if (start != MIN + 1) res.add(new Seg(list.get(i).pos, start, end));
        i = j;
    }
    //注意这里不能这么写。。。
    //list = res;
    //得这么写才行
    list.clear();
    list.addAll(res);
    return sum;
}

} ```