#P3214. 最少数量线段覆盖(200分)
-
1000ms
Tried: 150
Accepted: 26
Difficulty: 7
所属公司 :
华为od
最少数量线段覆盖(200分)
题目描述
给定坐标轴上的一组线段,每个线段的起点和终点均为整数,并且长度不小于 1。请你从中找到最少数量的线段,这些线段可以覆盖所有给定的线段。
输入描述
- 第一行输入为所有线段的数量 ( N )(不超过 10000)。
- 后面每行表示一条线段,格式为 "x,y",其中 ( x ) 和 ( y ) 分别表示线段的起点和终点,取值范围是 ([-10^5, 10^5])。
输出描述
- 输出最少线段数量,为正整数。
解题思路
-
排序:
- 首先,对所有线段的起点进行排序,如果起点相同,则按终点排序。这一步确保我们可以按照顺序处理线段,方便后续的比较。
-
使用栈:
- 创建一个栈来记录被选择的线段。在遍历每个线段时,进行以下分类讨论:
- 情况一: 当前线段完全覆盖栈顶线段,弹出栈顶元素,继续比较当前线段与新的栈顶元素。
- 情况二: 当前线段与栈顶线段有部分交集。将当前线段去除与栈顶线段的交集部分,更新栈顶元素的结束点。
- 情况三: 当前线段完全被栈顶线段覆盖,直接忽略当前线段。
- 情况四: 当前线段与栈顶线段没有交集,直接将当前线段压入栈中。
- 创建一个栈来记录被选择的线段。在遍历每个线段时,进行以下分类讨论:
-
结果:
- 遍历完所有线段后,栈的大小即为覆盖所有线段所需的最少线段数量。
复杂度分析
-
时间复杂度:
- 排序需要 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 分别表示起点和终点,取值范围是 [−105,105] 。
输出描述
最少线段数量,为正整数
样例1
输入
3
1,4
2,5
3,6
输出
2