题目描述

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

输入描述

• 第一行输入为所有线段的数量 ( N )（不超过 10000）。
• 后面每行表示一条线段，格式为 "x,y"，其中 ( x ) 和 ( y ) 分别表示线段的起点和终点，取值范围是 ([-10^5, 10^5])。

输出描述

• 输出最少线段数量，为正整数。

解题思路

1. 排序:

   • 首先，对所有线段的起点进行排序，如果起点相同，则按终点排序。这一步确保我们可以按照顺序处理线段，方便后续的比较。

2. 使用栈:

   • 创建一个栈来记录被选择的线段。在遍历每个线段时，进行以下分类讨论：
     • 情况一: 当前线段完全覆盖栈顶线段，弹出栈顶元素，继续比较当前线段与新的栈顶元素。
     • 情况二: 当前线段与栈顶线段有部分交集。将当前线段去除与栈顶线段的交集部分，更新栈顶元素的结束点。
     • 情况三: 当前线段完全被栈顶线段覆盖，直接忽略当前线段。
     • 情况四: 当前线段与栈顶线段没有交集，直接将当前线段压入栈中。

3. 结果:

   • 遍历完所有线段后，栈的大小即为覆盖所有线段所需的最少线段数量。

复杂度分析

• 时间复杂度:

  • 排序需要 O(N log N)，遍历线段并使用栈的过程为 O(N) 。因此，总的时间复杂度为 O(N log N)。

• 空间复杂度:

  • 使用栈存储线段，最坏情况下栈的大小可能达到 O(N)，所以空间复杂度为 O(N) 。

代码实现

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    // 使用 pair 表示每个线段的起始和结束点
    vector<pair<int, int>> segments(n);
    char comma; // 用于读取逗号

    // 输入读取
    for (int i = 0; i < n; i++) {
        cin >> segments[i].first >> comma >> segments[i].second;
    }

    // 按起始点排序线段，如果起始点相同，则按结束点排序
    sort(segments.begin(), segments.end());

    // 使用双端队列管理重叠的线段
    deque<pair<int, int>> stack;
    stack.push_back(segments[0]); // 将第一个线段放入栈中

    for (int i = 1; i < segments.size(); i++) {
        pair<int, int> segment = segments[i]; // 当前线段

        while (true) {
            if (stack.empty()) {
                stack.push_back(segment); // 如果栈为空，则直接推入当前线段
                break;
            }

            pair<int, int> top = stack.back(); // 获取栈顶线段
            int s0 = top.first; // 栈顶线段的起始点
            int e0 = top.second; // 栈顶线段的结束点
            int s1 = segment.first; // 当前线段的起始点
            int e1 = segment.second; // 当前线段的结束点

            // 情况 1: 当前线段完全覆盖栈顶线段
            if (s1 <= s0) {
                if (e1 <= e0) {
                    break; // 当前线段在栈顶线段内，且没有扩展
                } else {
                    stack.pop_back(); // 当前线段更大，移除栈顶
                }
            }
            // 情况 2: 当前线段在栈顶线段内并扩展了栈顶线段
            else if (s1 < e0) {
                if (e1 <= e0) {
                    break; // 当前线段在栈顶线段内，且没有扩展
                } else {
                    stack.push_back({e0, e1}); // 合并并扩展
                    break;
                }
            }
            // 情况 3: 当前线段在栈顶线段之后
            else {
                stack.push_back(segment); // 将当前线段推入栈中
                break;
            }
        }
    }

    // 栈的大小表示所需的最小线段数量
    cout << stack.size() << endl;

    return 0;
}

Java 代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取线段数量
        int n = Integer.parseInt(scanner.nextLine());
        List<int[]> segments = new ArrayList<>();

        // 输入读取
        for (int i = 0; i < n; i++) {
            String line = scanner.nextLine();
            String[] parts = line.split(",");
            int x = Integer.parseInt(parts[0]);
            int y = Integer.parseInt(parts[1]);
            segments.add(new int[]{x, y});
        }

        // 按起始点排序线段，如果起始点相同，则按结束点排序
        Collections.sort(segments, Comparator.comparingInt(a -> a[0]));

        // 使用栈管理重叠的线段
        Stack<int[]> stack = new Stack<>();
        stack.push(segments.get(0)); // 将第一个线段放入栈中

        for (int i = 1; i < n; i++) {
            int[] segment = segments.get(i); // 当前线段

            while (true) {
                if (stack.isEmpty()) {
                    stack.push(segment); // 如果栈为空，则直接推入当前线段
                    break;
                }

                int[] top = stack.peek(); // 获取栈顶线段
                int s0 = top[0]; // 栈顶线段的起始点
                int e0 = top[1]; // 栈顶线段的结束点
                int s1 = segment[0]; // 当前线段的起始点
                int e1 = segment[1]; // 当前线段的结束点

                // 情况 1: 当前线段完全覆盖栈顶线段
                if (s1 <= s0) {
                    if (e1 <= e0) {
                        break; // 当前线段在栈顶线段内，且没有扩展
                    } else {
                        stack.pop(); // 当前线段更大，移除栈顶
                    }
                }
                // 情况 2: 当前线段在栈顶线段内并扩展了栈顶线段
                else if (s1 < e0) {
                    if (e1 <= e0) {
                        break; // 当前线段在栈顶线段内，且没有扩展
                    } else {
                        stack.push(new int[]{e0, e1}); // 合并并扩展
                        break;
                    }
                }
                // 情况 3: 当前线段在栈顶线段之后
                else {
                    stack.push(segment); // 将当前线段推入栈中
                    break;
                }
            }
        }

        // 栈的大小表示所需的最小线段数量
        System.out.println(stack.size());
    }
}

Python 代码

def main():
    n = int(input())  # 读取线段数量
    segments = []

    # 输入读取
    for _ in range(n):
        line = input()
        x, y = map(int, line.split(','))
        segments.append((x, y))

    # 按起始点排序线段，如果起始点相同，则按结束点排序
    segments.sort()

    # 使用栈管理重叠的线段
    stack = []
    stack.append(segments[0])  # 将第一个线段放入栈中

    for i in range(1, n):
        segment = segments[i]  # 当前线段
        while True:
            if not stack:
                stack.append(segment)  # 如果栈为空，则直接推入当前线段
                break

            top = stack[-1]  # 获取栈顶线段
            s0, e0 = top  # 栈顶线段的起始点和结束点
            s1, e1 = segment  # 当前线段的起始点和结束点

            # 情况 1: 当前线段完全覆盖栈顶线段
            if s1 <= s0:
                if e1 <= e0:
                    break  # 当前线段在栈顶线段内，且没有扩展
                else:
                    stack.pop()  # 当前线段更大，移除栈顶
            # 情况 2: 当前线段在栈顶线段内并扩展了栈顶线段
            elif s1 < e0:
                if e1 <= e0:
                    break  # 当前线段在栈顶线段内，且没有扩展
                else:
                    stack.append((e0, e1))  # 合并并扩展
                    break
            # 情况 3: 当前线段在栈顶线段之后
            else:
                stack.append(segment)  # 将当前线段推入栈中
                break

    # 栈的大小表示所需的最小线段数量
    print(len(stack))

if __name__ == "__main__":
    main()

题目内容

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

输入描述

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

输出描述

最少线段数量，为正整数

样例1

输入

3
1,4
2,5
3,6

输出

2