题目描述
给定坐标轴上的一组线段,线段的起点和终点均为整数并且长度不小于1,请你从中找到最少数量的线段,这些线段可以覆盖住所有线段。
输入描述
第一行输入为所有线段的数量,不超过10000,后面每行表示一条线段,格式为”x,y”,
x和y 分别表示起点和终点,取值范围是[-10^5 ,10^5]。
输出描述最少线段数量,为正整数。
输入
3
1,4
2,5
3,6
输出
2
题意解读
首先,用示例来理解题意:现在有三条线段:
一号线段:起点1,终点4;
二号线段:起点2,终点5;
三号线段:起点3,终点6;
我们要从这三条线段中,选出若干条线段,覆盖1~6
整个区间。
比如,我们可以选择 一号、二号、三号。一号覆盖 1~4
,二号覆盖 2~5
,三号覆盖3~6
,三条线段加起来可以覆盖1~6
整个区间。但是,题目要求尽可能选择少的线段。因此,我们只用选择一号、三号,也能覆盖1~6
整个区间。所以,答案就是选择2
条线段(即一号、三号)。
解题思路
这是一道典型的贪心算法,贪心策略如下:
首先,将所有线段按起点从小到大排序。
然后遍历排序后的线段,每遍历到一个线段(我们称当前正在遍历的线段为current
线段),找出后面的线段中左端点小于等于current
线段的右端点的所有线段(我们称之为备选线段),找出备选线段中右端点最大的一个线段maxLine
。下一步遍历maxLine
。
不断重复以上操作,直到覆盖完整个长度为m的区间,就能得到最少的线段数。
视频讲解
2023华为机试真题【区间交叠/贪心算法】
示例代码(Java版本)
import java.util.*;
public class Main {
static class Line implements Comparable<Line> {
int start;
int end;
public Line(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Line other) {
return Integer.compare(this.start, other.start);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Line> lines = new ArrayList<>();
for (int i = 0; i < n; i++) {
String input = scanner.next();
String[] points = input.split(",");
int start = Integer.parseInt(points[0]);
int end = Integer.parseInt(points[1]);
lines.add(new Line(start, end));
}
// 按照起点从小到大排序
Collections.sort(lines);
int minSegments = 0;
int currentEnd = Integer.MIN_VALUE;
for (Line line : lines) {
// 如果当前线段的起点小于等于当前覆盖的终点,则更新当前的覆盖终点
if (line.start <= currentEnd) {
currentEnd = Math.max(currentEnd, line.end);
} else {
// 否则,当前线段不能延伸到当前覆盖终点,需要选择这个线段并更新当前覆盖终点
minSegments++;
currentEnd = line.end;
}
}
// 最后一个线段也需要计入结果
minSegments++;
System.out.println(minSegments);
}
}
示例代码(Python版本)
class Line:
def __init__(self, start, end):
self.start = start
self.end = end
def __lt__(self, other):
return self.start < other.start
def main():
n = int(input())
lines = []
for _ in range(n):
start, end = map(int, input().split(','))
lines.append(Line(start, end))
# 按照起点从小到大排序
lines.sort()
min_segments = 0
current_end = float('-inf')
for line in lines:
# 如果当前线段的起点小于等于当前覆盖的终点,则更新当前的覆盖终点
if line.start <= current_end:
current_end = max(current_end, line.end)
else:
# 否则,当前线段不能延伸到当前覆盖终点,需要选择这个线段并更新当前覆盖终点
min_segments += 1
current_end = line.end
# 最后一个线段也需要计入结果
min_segments += 1
print(min_segments)
if __name__ == "__main__":
main()
示例代码(C++版本)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Line {
int start;
int end;
Line(int start, int end) : start(start), end(end) {}
bool operator<(const Line& other) const {
return start < other.start;
}
};
int main() {
int n;
cin >> n;
vector<Line> lines;
for (int i = 0; i < n; i++) {
int start, end;
char comma;
cin >> start >> comma >> end;
lines.push_back(Line(start, end));
}
// 按照起点从小到大排序
sort(lines.begin(), lines.end());
int minSegments = 0;
int currentEnd = INT_MIN;
for (const Line& line : lines) {
// 如果当前线段的起点小于等于当前覆盖的终点,则更新当前的覆盖终点
if (line.start <= currentEnd) {
currentEnd = max(currentEnd, line.end);
} else {
// 否则,当前线段不能延伸到当前覆盖终点,需要选择这个线段并更新当前覆盖终点
minSegments++;
currentEnd = line.end;
}
}
// 最后一个线段也需要计入结果
minSegments++;
cout << minSegments << endl;
return 0;
}
文章出处登录后可见!
已经登录?立即刷新