题目描述
给定坐标轴上的一组线段，线段的起点和终点均为整数并且长度不小于1，请你从中找到最少数量的线段，这些线段可以覆盖柱所有线段。
输入描述
第一行输入为所有线段的数量，不超过10000，后面每行表示一条线段，格式为"x,y"，x和y分别表示起点和终点，取值范围是[-10^5，10^5]。
输出描述
最少线段数量，为正整数
用例
| 输入 |
3 |
| 输出 | 2 |
| 说明 | 无 |
题目解析
用例1图示如下
可以发现，只要选择[]1,4[和[3,6]就可以覆盖住所有给定线段。
我的解题思路如下：
首先，将所有区间ranges按照开始位置升序。
然后，创建一个辅助的栈stack，初始时将排序后的第一个区间压入栈中。
然后，遍历出1~ranges.length范围内的每一个区间ranges[i]，将遍历到ranges[i]和stack栈顶区间对比：
- 如果stack栈顶区间可以包含ranges[i]区间，则range[i]不压入栈顶
- 如果stack栈顶区间被ranges[i]区间包含，则弹出stack栈顶元素，继续比较ranges[i]和stack新的栈顶元素
- 如果stack栈顶区间和ranges[i]无法互相包含，只有部分交集，则将ranges[i]区间去除交集部分后，剩余部分区间压入stack
- 如果stack栈顶区间和ranges[i]区间没有交集，那么直接将ranges[i]压入栈顶
这样的话，最终stack中有多少个区间，就代表至少需要多少个区间才能覆盖所有线段。
比如，用例1的运行流程如下：
2,5 和 1,4 存在重叠区间，我们只保留2,5区间的非重叠部分4,5
比较4,5区间和3,6区间，发现3,6完全涵盖2,5,因此2,5区间不再需要，可以从stack中弹栈删掉，即原始的2,5区间被删除了。
继续比较1,4和3,6区间，发现无法互相涵盖，因此都需要保留，但是3,6有部分区间和1,4重叠，因此只保留3,6不重叠部分4,6。
最终只需要两个区间，对应1,4、3,6，即可涵盖所有线段
自测用例：
8
0,4
1,2
1,4
3,7
6,8
10,12
11,13
12,14
输出5，即至少需要上面标红的五个区间才能覆盖所有线段。
2023.01.27
根据网友指正，上面逻辑缺失一个场景，比如：
3
1,10
5,12
8,11
按找前面逻辑，首先对所有区间按开始位置升序，然后将1,10入栈
然后尝试将5,12入栈，发现和栈顶区间有交集，因此去除交集部分后，5,12变为10,12，入栈
然后尝试将8,11入栈，但是此时出现一个尴尬的情况，那就是栈顶区间10,12不能完全包含8,11，因此8,11区间还需要和栈顶前一个区间1,10继续比较，这就背离了我们一开始将所有区间按开始位置升序的初衷了。。。
而导致这个问题的根本原因是，栈顶区间10,12是被裁剪过的，因此导致它的起始位置落后了，即可能无法包含住升序后下一个区间的起始位置了，但是转念一想，先入栈的区间的起始位置肯定是要小于等于后入栈的区间的，因此栈顶区间被裁剪，说明栈顶区间和前一个区间必然是严密结合的，因此8,11的起始位置超出了栈顶区间，其实还是会被栈顶前一个区间包含进去。因此这里8,11不入栈。
JavaScript算法源码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
let n;
rl.on("line", (line) => {
lines.push(line);
if (lines.length === 1) {
n = lines[0] - 0;
}
if (n && lines.length === n + 1) {
lines.shift();
const ranges = lines.map((line) => line.split(",").map(Number));
console.log(getResult(ranges, n));
lines.length = 0;
}
});
function getResult(ranges, n) {
ranges.sort((a, b) => a[0] - b[0]);
const stack = [ranges[0]];
for (let i = 1; i < ranges.length; i++) {
const range = ranges[i];
while (true) {
if (stack.length == 0) {
stack.push(range);
break;
}
const [s0, e0] = stack.at(-1);
const [s1, e1] = range;
if (s1 <= s0) {
if (e1 <= s0) {
break;
} else if (e1 < e0) {
break;
} else {
stack.pop();
}
} else if (s1 < e0) {
if (e1 <= e0) {
break;
} else {
stack.push([e0, e1]);
break;
}
} else {
stack.push(range);
break;
}
}
}
//console.log(stack);
return stack.length;
}
Java算法源码
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
Integer[][] ranges = new Integer[n][];
for (int i = 0; i < n; i++) {
ranges[i] =
Arrays.stream(sc.nextLine().split(",")).map(Integer::parseInt).toArray(Integer[]::new);
}
System.out.println(getResult(ranges));
}
public static int getResult(Integer[][] ranges) {
Arrays.sort(ranges, (a, b) -> a[0] - b[0]);
LinkedList<Integer[]> stack = new LinkedList<>();
stack.add(ranges[0]);
for (int i = 1; i < ranges.length; i++) {
Integer[] range = ranges[i];
while (true) {
if (stack.size() == 0) {
stack.add(range);
break;
}
Integer[] top = stack.getLast();
int s0 = top[0];
int e0 = top[1];
int s1 = range[0];
int e1 = range[1];
if (s1 <= s0) {
if (e1 <= s0) {
break;
} else if (e1 < e0) {
break;
} else {
stack.removeLast();
}
} else if (s1 < e0) {
if (e1 <= e0) {
break;
} else {
stack.add(new Integer[] {e0, e1});
break;
}
} else {
stack.add(range);
break;
}
}
}
return stack.size();
}
}
Python算法源码
# 输入获取
n = int(input())
rans = [list(map(int, input().split(","))) for i in range(n)]
# 算法入口
def getResult(rans, n):
rans.sort(key=lambda x: x[0])
stack = [rans[0]]
for i in range(1, n):
ran = rans[i]
while True:
if len(stack) == 0:
stack.append(ran)
break
s0, e0 = stack[-1]
s1, e1 = ran
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(ran)
break
return len(stack)
# 算法调用
print(getResult(rans, n))
免责声明：
评论0