华为OD机试 - 最少数量线段覆盖 - 二叉树（Java 2023 B卷 100分 考试抽中题）

目录

• • 一、题目描述
  • 二、输入描述
  • 三、输出描述
  • 四、解题思路
  • 四、Java算法源码
  • 五、效果展示

一、题目描述

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

二、输入描述

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

三、输出描述

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

四、解题思路

1. 定义一个节点，有左节点和右节点两个属性；
2. 在Node类中定义compareTo方法，比较Node左节点；
   • 如果当前node和参数node的左节点相当，返回参数右节点与当前的右节点差；
   • 如果当前node和参数node的左节点不相当，返回当前node和参数node的左节点的差值；
3. 输入所有线段的数量n；
4. 输入n个Node节点，有两个值，起点和终点；
5. 将输入的Node节点进行排序，根据Node左节点进行升序排列；
6. 定义变量right，记录第一个节点的右节点；
7. 定义变量maxRight，记录最大右节点，初始化为第一个节点的右节点；
8. 遍历节点集合arr；
9. 如果之后的右节点大于第一个右节点；
10. 比较最大右节点与当前的右节点；
11. 获取最大右节点；
12. 循环往复，最后输出最少线段数量。

四、Java算法源码

public static void main(String[] args) {
    Node[] arr = new Node[10000];
    Scanner sc = new Scanner(System.in);
    // 输入所有线段的数量n
    int n = sc.nextInt();
    // 输入n个Node节点，有两个值，起点和终点
    for (int i = 0; i < n; i++) {
        String[] s = sc.next().split(",");
        arr[i] = new Node(Integer.parseInt(s[0]), Integer.parseInt(s[1]));
    }
    
    // 将输入的Node节点进行排序，根据Node左节点进行升序排列
    Arrays.sort(arr, 0, n - 1);

    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;
    }

    /**
     * 和当前结点进行比较
     * 如果当前node和参数node的左节点相当，返回参数右节点与当前的右节点差
     * 如果当前node和参数node的左节点不相当，返回当前node和参数node的左节点的差值
     * @param o
     * @return
     */
    @Override
    public int compareTo(Node o) {
        if (l == o.l) {
            return o.r - r;
        }
        return l - o.l;
    }
}

五、效果展示

1、输入

3
1,7
3,6
8,9

2、输出

2

3、说明

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

4、复杂一点

6
15,20
3,6
8,12
1,7
11,15
18,20

5、理性分析一下

先按照节点Node的左节点进行升序排序。

6
1,7
3,6
8,12
11,15
15,20
18,20

1. 一共6行数据；
2. 第一行1,7全包含第二行3,6 — 1,7；
3. 第三行8,12，与1,7无覆盖，故输出1,7 + 8,12；
4. 第四行11,15，不能全覆盖，故输出1,7 + 8,12 + 11,15；
5. 第五行15,20，不能全覆盖，故输出1,7 + 8,12 + 11,15 + 15,20；
6. 第六行18,20，被15,20覆盖，故弃用，最后输出1,7 + 8,12 + 11,15 + 15,20，，共最少线段数量 = 4个。

你觉得对吗，自己测试一下吧

🏆下一篇：华为OD机试真题 Java 实现【简易内存池】【2023 B卷 200分 考生抽中题】

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。