Commit5e39e08

zhenyu zhang

committed

update Solution 56、57

1 parent4f8a8e9 commit5e39e08Copy full SHA for 5e39e08

File tree

+88

-0

lines changed

+88

-0

lines changed

Lines changed: 43 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,43 @@`
	`1`	`+packagecom.hadley.top100;`
	`2`	`+`
	`3`	`+/*`
	`4`	`+2020.11.19`
	`5`	`+56、Merge Intervals`
	`6`	`+Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.`
	`7`	`+`
	`8`	`+Example 1:`
	`9`	`+Input: intervals = [[1,3],[2,6],[8,10],[15,18]]`
	`10`	`+Output: [[1,6],[8,10],[15,18]]`
	`11`	`+Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].`
	`12`	`+`
	`13`	`+Example 2:`
	`14`	`+Input: intervals = [[1,4],[4,5]]`
	`15`	`+Output: [[1,5]]`
	`16`	`+Explanation: Intervals [1,4] and [4,5] are considered overlapping.`
	`17`	`+ */`
	`18`	`+`
	`19`	`+importjava.util.ArrayList;`
	`20`	`+importjava.util.Arrays;`
	`21`	`+`
	`22`	`+`
	`23`	`+publicclass_056 {`
	`24`	`+`
	`25`	`+publicint[][]merge(int[][]intervals) {`
	`26`	`+ArrayList<int[]>result =newArrayList<>();`
	`27`	`+if(intervals ==null \|\|intervals.length <2){`
	`28`	`+returnintervals;`
	`29`	`+ }`
	`30`	`+//sort the intervals`
	`31`	`+Arrays.sort(intervals, (a,b) ->a[0] -b[0]);`
	`32`	`+for(int[]interval:intervals){`
	`33`	`+if(result.size() ==0 \|\|result.get(result.size() -1)[1] <interval[0]){`
	`34`	`+result.add(interval);`
	`35`	`+ }else{`
	`36`	`+result.get(result.size() -1)[1] =Math.max(result.get(result.size() -1)[1],interval[1]);`
	`37`	`+ }`
	`38`	`+ }`
	`39`	`+`
	`40`	`+returnresult.toArray(newint[result.size()][2]);`
	`41`	`+`
	`42`	`+ }`
	`43`	`+}`

Lines changed: 45 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,45 @@`
	`1`	`+packagecom.hadley.top100;`
	`2`	`+`
	`3`	`+/*`
	`4`	`+2020.11.19`
	`5`	`+57、Insert Interval`
	`6`	`+Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).`
	`7`	`+`
	`8`	`+You may assume that the intervals were initially sorted according to their start times.`
	`9`	`+`
	`10`	`+Example 1:`
	`11`	`+Input: intervals = [[1,3],[6,9]], newInterval = [2,5]`
	`12`	`+Output: [[1,5],[6,9]]`
	`13`	`+`
	`14`	`+Example 2:`
	`15`	`+Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]`
	`16`	`+Output: [[1,2],[3,10],[12,16]]`
	`17`	`+Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].`
	`18`	`+`
	`19`	`+Example 3:`
	`20`	`+Input: intervals = [], newInterval = [5,7]`
	`21`	`+Output: [[5,7]]`
	`22`	`+`
	`23`	`+Example 4:`
	`24`	`+Input: intervals = [[1,5]], newInterval = [2,3]`
	`25`	`+Output: [[1,5]]`
	`26`	`+`
	`27`	`+Example 5:`
	`28`	`+Input: intervals = [[1,5]], newInterval = [2,7]`
	`29`	`+Output: [[1,7]]`
	`30`	`+ */`
	`31`	`+`
	`32`	`+importjava.util.ArrayList;`
	`33`	`+`
	`34`	`+publicclass_057 {`
	`35`	`+`
	`36`	`+publicint[][]insert(int[][]intervals,int[]newInterval) {`
	`37`	`+ArrayList<int[]>result =newArrayList<>();`
	`38`	`+//newInterval[0], newInterval[1]`
	`39`	`+for(int[]interval:intervals){`
	`40`	`+//TODO`
	`41`	`+ }`
	`42`	`+`
	`43`	`+returnresult.toArray(newint[result.size()][2]);`
	`44`	`+ }`
	`45`	`+}`

Comments

(0)