Coursera算法工具盒第3周收集签名题Java实现超时求优化

问题背景 #

该问题来自Coursera的Algorithmic toolbox第3周（Collecting Signatures/收集签名）。

问题描述 #

给定数轴上坐标为整数的𝑛个线段构成的集合{[𝑎₀, 𝑏₀], [𝑎₁, 𝑏₁], …, [𝑎ₙ₋₁, 𝑏ₙ₋₁]}，求最少的点数量𝑚，使得每个线段至少包含一个点。即找到规模最小的整数集合𝑋，对任意线段[𝑎ᵢ, 𝑏ᵢ]，都存在点𝑥 ∈ 𝑋满足𝑎ᵢ ≤ 𝑥 ≤ 𝑏ᵢ。

现存性能问题 #

原有代码手写选择排序实现线段按起点排序，时间复杂度为O(n²)，n=100量级时运行效率就已明显降低，业务逻辑无错误，小输入样本可正常输出结果。

优化思路 #

• 替换排序实现：放弃手写O(n²)的选择排序，使用Java内置的Timsort（时间复杂度O(nlogn)）完成排序。为了保证线段起止点的对应关系，直接用二维数组存储每个线段的起止点，按线段右端点升序排序，符合该题标准贪心策略的排序要求，也可以进一步简化后续选点逻辑。
• 简化贪心逻辑：按右端点排序后，每次取当前第一个未覆盖线段的右端点作为选点，直接跳过所有包含该点的后续线段即可，无需额外回退索引。

优化后完整代码 #

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

class CoveringSegments {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        // 用二维数组存储每个线段的[起点, 终点]
        int[][] segments = new int[n][2];
        for (int i = 0; i < n; i++) {
            segments[i][0] = scanner.nextInt();
            segments[i][1] = scanner.nextInt();
        }
        // 按线段右端点升序排序，O(nlogn)时间复杂度
        Arrays.sort(segments, Comparator.comparingInt(a -> a[1]));
        
        List<Integer> points = getMinPoints(segments);
        System.out.println(points.size());
        for (Integer point : points) {
            System.out.print(point + " ");
        }
        scanner.close();
    }

    public static List<Integer> getMinPoints(int[][] segments) {
        List<Integer> points = new ArrayList<>();
        int n = segments.length;
        int index = 0;
        while (index < n) {
            // 取当前未覆盖线段的右端点作为选点
            int currentPoint = segments[index][1];
            points.add(currentPoint);
            // 跳过所有包含当前选点的线段
            while (index < n && segments[index][0] <= currentPoint && segments[index][1] >= currentPoint) {
                index++;
            }
        }
        return points;
    }
}

性能提升说明 #

优化后排序部分的时间复杂度从O(n²)降到O(nlogn)，n=1e4量级也能毫秒级返回结果，整体逻辑和原题贪心策略完全对齐，正确性和效率都有保障。

内容的提问来源于stack exchange，提问作者Bhavil Ahuja