int st = -2e9, ed = -2e9; for (auto seg : segs) if (ed < seg.first) { if (st != -2e9) res.push_back({st, ed}); st = seg.first, ed = seg.second; } else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res; }
题目
AcWing
805 区间合并
805
描述
给定 n 个区间 ,要求合并所有有交集的区间。
注意如果在端点处相交,也算有交集。
输出合并完成后的区间个数。
例如:[1,3]和[2,6]可以合并为一个区间[1,6]。
解答
import java.util.*; import java.io.*;
publicclassMain{ publicstaticvoidmain(String[] args)throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); // nums[0]左端点 nums[1]右端点 int[][] nums = newint[n][2]; for(int i=0;i<n;i++) { String[] strs = br.readLine().split(" "); nums[i][0] = Integer.parseInt(strs[0]); nums[i][1] = Integer.parseInt(strs[1]); } Arrays.sort(nums, new Comparator<int[]>(){ publicintcompare(int[] o1, int[] o2){ return o1[0]-o2[0]; } }); int end = Integer.MIN_VALUE; int sum = 0; for(int st=0;st<n;st++){ if(nums[st][0]>end){ //无法合并 sum++; } //跟新end end = Math.max(end, nums[st][1]); } System.out.println(sum); } }