华为OD机试真题B卷 Java 实现【最少数量线段覆盖】，附详细解题思路

华为OD机试真题B卷 Java 实现【最少数量线段覆盖】，附详细解题思路-LMLPHP

一、题目描述

给定坐标轴上的一组线段，线段的起点和终点均为整数并且长度不小于1，请你从中找到最少数量的线段，这些线段可以覆盖住所有线段。

二、输入描述

第一行输入为所有线段的数量，不超过10000，后面每行表示一条线段，格式为"x,y"，x和y分别表示起点和终点，取值范围是[-105,105]。

三、输出描述

最少线段数量，为正整数。

四、解题思路

创建一个 Node 类用于表示线段的起点和终点；
读取输入的线段数量 n；
使用循环读取每条线段的起点和终点，并将其存储到 arr 数组中；
对 arr 数组进行排序，按照线段的起点升序排序，如果起点相同，则按照终点降序排序；
如果线段数量 n 为0，直接输出0；
否则，初始化结果数量 ret 为1，表示至少需要一条线段；
初始化变量 right 和 maxRight 为第一条线段的终点 r；
使用循环从第二条线段开始遍历；
如果当前线段的起点 l 大于 right，表示当前线段与前一个线段不相连，需要新增一条线段；
- 如果 maxRight 大于 right，表示存在未覆盖的线段，新增一条线段，将 right 更新为 maxRight；
- 如果 maxRight 小于当前线段的起点 l，表示当前线段与前一个线段之间有未覆盖的空隙，新增一条线段，将 right 更新为当前线段的终点 r；
更新 maxRight 为当前线段的终点 r；
如果 maxRight 大于 right，表示最后一个线段没有被覆盖，新增一条线段；
输出结果数量 ret；

五、Java算法源码

public static void main(String[] args) {
    Node[] arr = new Node[10000];
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    for (int i = 0; i < n; i++) {
        String[] s = sc.next().split(",");
        arr[i] = new Node(Integer.parseInt(s[0]), Integer.parseInt(s[1]));
    }

    Arrays.sort(arr, 0, n - 1);

    if (n == 0) {
        System.out.println(0);
    } else {
        int ret = 1;
        int right = arr[0].r;
        int maxRight = arr[0].r;
        for (int i = 1; i < n; i++) {
            if (arr[i].l > right) {
                if (maxRight > right) {
                    ret++;
                    right = maxRight;
                }
                if (maxRight < arr[i].l) {
                    ret++;
                    right = arr[i].r;
                }
            }
            maxRight = Math.max(arr[i].r, maxRight);
        }
        if (maxRight > right) {
            ret++;
        }
        System.out.println(ret);
    }
}

static class Node implements Comparable<Node> {
    int l, r;

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

    @Override
    public int compareTo(Node o) {
        if (l == o.l) {
            return o.r - r;
        }
        return l - o.l;
    }
}

六、效果展示

1、输入

3
1,5
3,6
5,7

2、输出

3、说明

选取2条线段[1,5]和[5,7]即可，这两条线段可以覆盖[3,6]。