2023年华为OD机考真题：最少数量线段覆盖

算法刷题1年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：最少数量线段覆盖
知识点排序贪心
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
给定坐标轴上的一组线段，线段的起点和终点均为整数并且长度不小于1，请你从中找到最少数量的线段，这些线段可以覆盖住所有线段。
输入描述：
第一行输入为所有线段的数量，不超过10000，后面每行表示一条线段，格式为”x,y”，x和y分别表示起点和终点，取值范围是[-105,105]。
输出描述：
最少线段数量，为正整数
示例1
输入：
3
1,4
2,5
3,6
输出：
2
说明：
选取2条线段[1,4]和[3,6]即可，这两条线段可以覆盖[2,5]
解题思路：
例如：
3
1,4
3,6
5,8
首先对上面的线段进行排序，排序的规则：
按照线段左节点升序排序
左节点相等的，按右节点降序排序
根据线段1，初始化right=4，maxRight=4，res=1；
线段2的左节点小于right，表示后面允许有某个线段与线段1来覆盖线段2；更新maxRight=6
线段3的左节点大于right，表示后面不可能有某个线段与right之前的线段来覆盖线段3（因为线段已经排过序了）：
因为maxRight>right，证明maxRight与right之间有线段没有被覆盖，所以res+1=2，right也更新为maxRight=6；
因为线段3的左节点小于maxRight，说明在maxRight之前有线段与线段3有交集，证明后面有覆盖的可能；更新maxRight=8；
最后因为maxRight=8>right=6；证明线段没有覆盖，res+1=3；
最终结果为3

代码实现：Java代码满分实现

package com.codernav.demo.hwod.exam;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @title 最少数量线段覆盖
 * @Description 给定坐标轴上的一组线段，线段的起点和终点均为整数并且长度不小于1，请你从中找到最少数量的线段，这些线段可以覆盖住所有线段。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    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(",");
            int v1 = Integer.parseInt(s[0]);
            int v2 = Integer.parseInt(s[1]);
            arr[i] = new Node(v1, v2);
        }
        Arrays.sort(arr, 0, n - 1);
        if (n == 0) {
            System.out.println(0);
        } else {
            int res = 1;
            //覆盖线段分界点（左侧已经被覆盖）
            int right = arr[0].r;
            //最大的右侧节点
            int maxRight = arr[0].r;
            for (int i = 1; i < n; i++) {
                if (arr[i].l > right) {
                    //说明right左侧的线段与线段arr[i]没有交集（无法进行覆盖了）
                    if (maxRight > right) {
                        //说明right到maxRight之间有线段之前没有覆盖，现在需要新的线段覆盖
                        res++;
                        //更新分界点为maxRight
                        right = maxRight;
                    }
                    if (maxRight < arr[i].l) {
                        //说明arr[i]跟前面所有的线段都没有交集，重新开始计算了
                        res++;
                        //分界点也要变成arr[i]的右节点（相当于初始化了）
                        right = arr[i].r;
                    }
                }
                //线段最右节点需要更新
                maxRight = Math.max(arr[i].r, maxRight);
            }
            if (maxRight > right) {
                //说明right到maxRight之间有线段还没有覆盖，需要再加一条
                res++;
            }
            System.out.println(res);
        }
    }

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