刷题笔记合集🔗

区间交叠问题

问题描述

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

输入格式

第一行输入为所有线段的数量，不超过10000，后面每行表示一条线段，格式为""， 和 分别表示起点和终点，取值范围是 。

输出格式

最少线段数量，为正整数。

样例输入

3
1,4
2,5
3,6

样例输出

2

数据范围

• 线段数量
• 线段端点取值范围
• 线段长度不小于1

题解

这道题目要求我们从给定的线段集合中选出最少数量的线段，使得它们能覆盖所有给定的线段。

首先，需要理解什么是"覆盖"：如果线段A完全包含在一条或多条选择的线段内，则称线段A被覆盖。

解决这个问题的关键是贪心策略。我们可以按照以下步骤处理：

1. 将所有线段按照起始位置升序排序
2. 维护一个栈（或列表）来保存需要的线段
3. 遍历排序后的每一条线段，与栈顶线段比较：
   • A. 如果当前线段与栈顶线段没有交集，则将当前线段入栈
   • B. 如果当前线段完全包含在栈顶线段内，则跳过当前线段
   • C. 如果当前线段与栈顶线段有部分交集，则保留未覆盖部分
   • D. 如果当前线段完全包含栈顶线段，则弹出栈顶元素，重新与新的栈顶元素比较

例如，对于样例输入:

3
1,4
2,5
3,6

执行过程如下：

1. 排序后的线段列表：[1,4], [2,5], [3,6]
2. 将第一条线段[1,4]入栈
3. 处理第二条线段[2,5]：
   • 它与栈顶线段[1,4]有交集
   • [2,5]的未覆盖部分是[4,5]，将其入栈
4. 处理第三条线段[3,6]：
   • 它完全包含栈顶线段[4,5]，弹出[4,5]
   • 比较[3,6]与新栈顶[1,4]，它们有交集
   • [3,6]的未覆盖部分是[4,6]，将其入栈
5. 最终栈中有[1,4]和[4,6]，需要2条线段

这个贪心策略的核心思想是尽可能利用现有线段的覆盖范围，只保留确实需要的部分。

算法的时间复杂度是O(n log n)，主要来自于对线段的排序。空间复杂度是O(n)，用于存储需要的线段。

对于给定的约束（线段数量不超过10000），这个算法可以高效地解决问题。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取线段数量
n = int(input())

# 读取所有线段
segments = []
for _ in range(n):
    x, y = map(int, input().split(','))
    segments.append([x, y])

# 按起始位置排序
segments.sort(key=lambda x: x[0])

# 求解函数
def min_covering_segments(segs):
    """
    计算覆盖所有线段所需的最少线段数
    
    参数:
        segs: 排序后的线段列表，每个线段为[start, end]形式
        
    返回:
        最少线段数量
    """
    if not segs:
        return 0
        
    # 初始化栈，放入第一个线段
    stack = [segs[0]]
    
    # 遍历剩余线段
    for i in range(1, len(segs)):
        seg = segs[i]
        
        # 处理每个线段时可能需要多次与栈顶比较
        while True:
            # 空栈时直接入栈
            if not stack:
                stack.append(seg)
                break
            
            s0, e0 = stack[-1]  # 栈顶线段
            s1, e1 = seg        # 当前线段
            
            # 当前线段起点在栈顶线段起点之前或相同
            if s1 <= s0:
                # 当前线段终点在栈顶线段起点之前，无法覆盖，跳过
                if e1 <= s0:
                    break
                # 当前线段终点在栈顶线段终点之前，被栈顶线段覆盖，跳过
                elif e1 < e0:
                    break
                # 当前线段完全包含栈顶线段，弹出栈顶，继续比较
                else:
                    stack.pop()
            # 当前线段起点在栈顶线段内部
            elif s1 < e0:
                # 当前线段被栈顶线段完全覆盖，跳过
                if e1 <= e0:
                    break
                # 当前线段部分被覆盖，添加未覆盖部分
                else:
                    stack.append([e0, e1])
                    break
            # 当前线段与栈顶线段无交集，直接入栈
            else:
                stack.append(seg)
                break
    
    # 返回需要的线段数量
    return len(stack)

# 输出结果
print(min_covering_segments(segments))

• Cpp

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

int main() {
    // 读取线段数量
    int n;
    cin >> n;
    
    // 读取所有线段
    vector<vector<int>> segs(n, vector<int>(2));
    for (int i = 0; i < n; i++) {
        string line;
        cin >> line;
        int pos = line.find(',');
        segs[i][0] = stoi(line.substr(0,