AcWing 1343. 挤牛奶区间合并Java
原题链接
简单
作者:
还想听你的故事
,
2021-01-16 21:15:53
,
所有人可见
,
阅读 530
import java.util.*;
public class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int nums[][]=new int[n][2];
for(int i=0;i<n;i++){
nums[i][0]=sc.nextInt();
nums[i][1]=sc.nextInt();
}
List<int[]>list=new ArrayList<>();
Arrays.sort(nums,(a,b)->a[0]-b[0]);
int temp[]=nums[0];
for(int i=1;i<n;i++){
if(temp[1]>=nums[i][0]) temp[1]=Math.max(temp[1],nums[i][1]);
else{
list.add(temp);
temp=nums[i];
}
}
list.add(temp);
int [][]res=list.toArray(new int[list.size()][]);
int sum1=0;
int sum2=0;
int max1=0;
int max2=0;
for(int i=0;i<res.length;i++){
sum1=res[i][1]-res[i][0];
if(i<res.length-1) sum2=res[i+1][0]-res[i][1];
max1=Math.max(max1,sum1);
max2=Math.max(max2,sum2);
}
System.out.println(max1+" "+max2);
}
}
写复杂了。求max1和max2这一步其实可以在区间合并的时候顺便做完~
是的。确实有点麻烦