2023华为OD机试真题【区间交叠/贪心算法】【Python Java】

题目描述

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

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

最少线段数量,为正整数。
输入
3
1,4
2,5
3,6
输出
2

题意解读

首先,用示例来理解题意:现在有三条线段:

一号线段:起点1,终点4;

二号线段:起点2,终点5;

三号线段:起点3,终点6;

在这里插入图片描述
我们要从这三条线段中,选出若干条线段,覆盖1~6整个区间。

比如,我们可以选择 一号、二号、三号。一号覆盖 1~4 ,二号覆盖 2~5,三号覆盖3~6,三条线段加起来可以覆盖1~6整个区间。但是,题目要求尽可能选择少的线段。因此,我们只用选择一号、三号,也能覆盖1~6整个区间。所以,答案就是选择2条线段(即一号、三号)。

解题思路

这是一道典型的贪心算法,贪心策略如下:

首先,将所有线段按起点从小到大排序。

然后遍历排序后的线段,每遍历到一个线段(我们称当前正在遍历的线段为current线段),找出后面的线段中左端点小于等于current线段的右端点的所有线段(我们称之为备选线段),找出备选线段中右端点最大的一个线段maxLine。下一步遍历maxLine

不断重复以上操作,直到覆盖完整个长度为m的区间,就能得到最少的线段数。

视频讲解

2023华为机试真题【区间交叠/贪心算法】

示例代码(Java版本)

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        sc.nextLine();
        
        Integer[][] segs = new Integer[n][];
        for (int i = 0; i < n; i++) {
            segs[i] = getSeg(sc.nextLine());
        }
        
        sort(segs);

        LinkedList<Integer[]> coverSegs = cover(segs);

        System.out.println(coverSegs.size());
    }

    private static Integer[] getSeg(String line) {
        String[] parts = line.split(",");
        return new Integer[]{Integer.parseInt(parts[0]), Integer.parseInt(parts[1])};
    }

    private static void sort(Integer[][] segs) {
        Arrays.sort(segs, (a, b) -> a[0].compareTo(b[0]));
    }

    private static LinkedList<Integer[]> cover(Integer[][] segs) {
        LinkedList<Integer[]> stack = new LinkedList<>();
        stack.add(segs[0]);

        for (int i = 1; i < segs.length; i++) {
            while (true) {
                if (stack.isEmpty()) {
                    stack.add(segs[i]);
                    break;
                }
                
                Integer[] top = stack.getLast();
                Integer[] cur = segs[i];

                if (cur[0] <= top[0]) {
                    if (cur[1] <= top[0]) {
                        break;
                    } else if (cur[1] < top[1]) {
                        break;
                    } else {
                        stack.removeLast();
                    }
                } else if (cur[0] < top[1]) {
                    if (cur[1] <= top[1]) {
                        break;
                    } else {
                        stack.add(new Integer[]{top[1], cur[1]});
                        break;
                    }
                } else {
                    stack.add(cur);
                    break;
                }
            }
        }

        return stack;
    }
}

示例代码(Python版本)

def get_segs(line):
    parts = line.split(",")
    return [int(parts[0]), int(parts[1])]

def sort_segs(segs):
    return sorted(segs, key=lambda x: x[0])

def cover(segs):
    stack = [segs[0]]

    for i in range(1, len(segs)):
        while True:
            if not stack:
                stack.append(segs[i])
                break

            top = stack[-1]
            cur = segs[i]

            if cur[0] <= top[0]:
                if cur[1] <= top[0]:
                    break
                elif cur[1] < top[1]:
                    break
                else:
                    stack.pop()
            elif cur[0] < top[1]:
                if cur[1] <= top[1]:
                    break
                else:
                    stack.append([top[1], cur[1]])
                    break
            else:
                stack.append(cur)
                break

    return stack

if __name__ == '__main__':
    n = int(input())
    segs = [get_segs(input()) for _ in range(n)]
    sorted_segs = sort_segs(segs)
    cover_segs = cover(sorted_segs)

    print(len(cover_segs))