侧边栏壁纸
博主头像
CoderKui

坐中静,舍中得,事上练

  • 累计撰写 51 篇文章
  • 累计创建 69 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

区间合并

CoderKui
2021-12-05 / 0 评论 / 0 点赞 / 263 阅读 / 411 字 / 正在检测是否收录...

区间合并

给定 n 个区间 ,要求合并所有有交集的区间。

注意如果在端点处相交,也算有交集。

输出合并完成后的区间个数。

例如:[1,3][1,3] 和 [2,6][2,6] 可以合并为一个区间 [1,6][1,6]。

方法:

  1. 按区间左端点排序
  2. 分三种情况讨论

经典例子:

给定 nn 个区间 [li,ri][li,ri],要求合并所有有交集的区间。

注意如果在端点处相交,也算有交集。

输出合并完成后的区间个数。

例如:[1,3][1,3] 和 [2,6][2,6] 可以合并为一个区间 [1,6][1,6]。

输入格式

第一行包含整数 nn。

接下来 nn 行,每行包含两个整数 ll 和 rr。

输出格式

共一行,包含一个整数,表示合并区间完成后的区间个数。

数据范围

1≤n≤1000001≤n≤100000,
−109≤li≤ri≤109−109≤li≤ri≤109

输入样例:

5
1 2
2 4
5 6
7 8
7 9

输出样例:

3
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<int[]> list = new ArrayList<>();
        for(int i = 0; i < n; ++i) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            list.add(new int[]{l, r});
        }
        int res = 0;
        list.sort((a, b) -> a[0] - b[0]);
        int st = (int)-2e9, ed = (int)-2e9;
        for(int i = 0; i < list.size(); ++i) {
            int[] tmp = list.get(i);
            if(ed < tmp[0]) {
                if(ed != -2e9) {
                    res++;
                }
                st = tmp[0];
                ed = tmp[1];
            } else {
                ed = Math.max(ed, tmp[1]);
            }
        }
        if(st != -2e9) res++;
        System.out.print(res);
    }
}
0

评论区