区间交叠问题
问题描述
给定坐标轴上的一组线段,线段的起点和终点均为整数并且长度不小于1,请你从中找到最少数量的线段,这些线段可以覆盖住所有线段。
输入描述
第一行输入为所有线段的数量,不超过10000,后面每行表示一条线段,格式为”x,y”,
x和y 分别表示起点和终点,取值范围是[-105,105]。
输出描述
最少线段数量,为正整数。
示例1
输入输出示例仅供调试,后台判题数据一般不包含示例
输入
3
1 4
2 5
3 6
输出
2
输入
4
1 3
2 4
4 8
5 9
输出
2
输入
3
1 6
2 5
5 7
输出
2
思路
先把所有线段按x值从小到大进行排序
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int[][] matrix =new int[m][2];
for (int i = 0; i < m; i++) {
matrix[i][0]=sc.nextInt();
matrix[i][1]=sc.nextInt();
}
//所有线段按x值从小到大进行排序
Arrays.stream(matrix).sorted((d1,d2)->{return d1[0]-d2[0];});
int x =matrix[0][0];
int y =matrix[0][1];
Integer max=null;
int num = 1;
for (int i = 1; i < matrix.length; i++) {
if (matrix[i][0]==x){
y=Math.max(y,matrix[i][1]);
}else {
if (y<matrix[i][0]){
num=0;
break;
}else {
max=Math.max(y,matrix[i][1]);
//当数组后面没线段 或 后面线段x大于定义y变量
if (i+1>=matrix.length||y<matrix[i+1][0]){
y=max;
num++;
}
}
}
}
System.out.println(num);
}