Loading...
世界已冷酷至极, 让我们携手前行。
自助收录

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

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

 

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

全网最全面的华为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;
        }
    }
}
 

 

© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...