56.マージ間隔（java）

56 Merging Interval

Given a set of intervals, please merge all overlapping intervals. Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: The intervals [1,3] and [2,6] overlap, and merge them into [1,6]. Example 2: Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: The intervals [1,4] and [4,5] can be considered as overlapping intervals. Source: LeetCode Link: https://leetcode-cn.com/problems/merge-intervals The copyright belongs to the deduction network. Please contact the official authorization for commercial reprint, and please indicate the source for non-commercial reprint.

解決策1：並べ替え

class Solution { public int[][] merge(int[][] intervals) { int[][] tmp = new int[intervals.length][2] Arrays.sort(intervals,new Comparator<int[]>(){ public int compare(int[] a,int[] b){ return a[0]-b[0] } }) int count = 0 int i=0,j=0 for(i = 0 i < intervals.length i++){ int left = intervals[i][0] int right = intervals[i][1] for(j = i+1 j < intervals.length j++){ if(intervals[j][0] > right) break if(right < intervals[j][1]) right = intervals[j][1] } tmp[count][0] = left tmp[count][1] = right count++ i = j-1 } return Arrays.copyOfRange(tmp, 0, count) } }

解決策2：マーキング方法、速くて理解しにくい

class Solution { public int[][] merge(int[][] intervals) { int len = intervals.length int count = 0 for(int i = 0 i < len i++) { for(int j = i+1 j < len j++){ if(isMerge(intervals, i, j)){ count++ break } } } int[][] res = new int[len-count][2] count = 0 for(int i = 0 i < len i++){ if(intervals[i][0] == 1 && intervals[i][1] == -1) continue res[count] = intervals[i] count++ } return res } public boolean isMerge(int[][] intervals, int begin, int end) { if(intervals[begin][0] == 1 && intervals[begin][1] == -1) return false if(intervals[end][0] == 1 && intervals[end][0] == -1) return false if(intervals[begin][0] < intervals[end][0] && intervals[begin][1] < intervals[end][0]) return false if(intervals[end][0] < intervals[begin][0] && intervals[end][1] < intervals[begin][0]) return false intervals[end][0] = Math.min(intervals[begin][0], intervals[end][0]) intervals[end][1] = Math.max(intervals[begin][1], intervals[end][1]) intervals[begin][0] = 1 intervals[begin][1] = -1 return true } }