系列文章目录
前言
本人最近再练习算法，所以会发布一些解题思路，希望大家多指教
一、题目描述
给定坐标轴上的一组线段，线段的起点和终点均为整数并且长度不小于1，请你从中找到最少数量的线段，这些线段可以覆盖住所有线段。
二、输入描述
第一行输入为所有线段的数量，不超过10000，后面每行表示一条线段，格式为"x,y"，x和y分别表示起点和终点，取值范围是[-105,105]。
三、输出描述
最少线段数量，为正整数。
四、java代码
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = Integer.parseInt(sc.nextLine());
List<int[]> list = new ArrayList<>();
for (int i = 0; i < N; i++) {
String[] split = sc.nextLine().split(" ");
list.add(new int[]{Integer.parseInt(split[0]), Integer.parseInt(split[1])});
}
//按照线段的左侧下标进行正序排序，相同时，按照右侧下标正序排序
list.sort(((o1, o2) -> {
if (o1[0]==o2[0]) {
return o1[1] - o2[1];
} else {
return o1[0] - o2[0];
}
}));
//初始化线段数量，默认都无法完成覆盖
int num = list.size();
for (int i = 0; i < list.size(); i++) {
int[] ints = list.get(i);
if(i+1 <list.size()){
//情况一：如果两个线段左侧下标相同，因为前面已经进行排序，所以后面的一定可以覆盖当前线段
if(ints[0] == list.get(i+1)[0]){
num--;
} else if(ints[1] >= list.get(i+1)[1]){
//情况二：如果右侧下标相同，则当前线段的一定可以覆盖下一个线段
num--;
//将下一个覆盖的线段的右侧下标进行延伸，继续向后比较
list.get(i+1)[1] = ints[1];
}
}
}
System.out.println(num);
}
五、测试用例
输入：
6
15 20
3 6
8 12
1 7
11 15
18 20
