LeetCode : 56. Merge Intervals 合并区间 矫情吗;* 2021-06-24 16:11 365阅读 0赞 **试题** Given a collection of intervals, merge all overlapping intervals. Example 1: Input: \[\[1,3\],\[2,6\],\[8,10\],\[15,18\]\] Output: \[\[1,6\],\[8,10\],\[15,18\]\] Explanation: Since intervals \[1,3\] and \[2,6\] overlaps, merge them into \[1,6\]. Example 2: Input: \[\[1,4\],\[4,5\]\] Output: \[\[1,5\]\] Explanation: Intervals \[1,4\] and \[4,5\] are considered overlapping. **代码** 根据实际合并逻辑,我们首先假想所有区间都放在一条数轴上,然后我们会从前往后开始合并。所以要对区间按左边界进行升序排序。 但是还有个问题是如果左边界相等时我们应该咋办?这是我们需要按右边界降序排序。之所以降序是为了避免出现左边界相等,但右边界过小,导致合并时错分为两个区间问题。 class Solution { public int[][] merge(int[][] intervals) { if(intervals==null || intervals.length==0) return new int[0][0]; Arrays.sort(intervals, (a,b) -> a[0]!=b[0]?a[0]-b[0]:b[1]-a[1] ); ArrayList<int[]> out = new ArrayList<>(); int[] tmp = intervals[0]; for(int i=1; i<intervals.length; i++){ if(intervals[i][0]<=tmp[1]){ tmp[1] = Math.max(tmp[1], intervals[i][1]); }else{ out.add(tmp); tmp = intervals[i]; } } out.add(tmp); return out.toArray(new int[out.size()][2]); } }
还没有评论,来说两句吧...