Commit45d9170

committed

add a solution for 435

1 parent9ca9c85 commit45d9170Copy full SHA for 45d9170

File tree

+30

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _435.java
- test/java/com/fishercoder
  - _435Test.java

+30

-0

lines changed

Lines changed: 20 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -27,4 +27,24 @@ public int eraseOverlapIntervals(int[][] intervals) {`
`27`	`27`	`}`
`28`	`28`	`}`
`29`	`29`
	`30`	`+publicstaticclassSolution2 {`
	`31`	`+/**`
	`32`	`+ * This is sorting my starting time, the key here is that we'll want to update end time when an erasure is needed:`
	`33`	`+ * we use the smaller end time instead of the bigger one which is more likely to overlap with others.`
	`34`	`+ */`
	`35`	`+publicinteraseOverlapIntervals(int[][]intervals) {`
	`36`	`+Arrays.sort(intervals, (a,b) ->a[0] !=b[0] ?a[0] -b[0] :a[1] -b[1]);`
	`37`	`+interasures =0;`
	`38`	`+intend =intervals[0][1];`
	`39`	`+for (inti =1;i <intervals.length;i++) {`
	`40`	`+if (intervals[i][0] <end) {`
	`41`	`+erasures++;`
	`42`	`+end =Math.min(end,intervals[i][1]);`
	`43`	`+ }else {`
	`44`	`+end =intervals[i][1];`
	`45`	`+ }`
	`46`	`+ }`
	`47`	`+returnerasures;`
	`48`	`+ }`
	`49`	`+ }`
`30`	`50`	`}`

Lines changed: 10 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -9,16 +9,26 @@`
`9`	`9`
`10`	`10`	`publicclass_435Test {`
`11`	`11`	`privatestatic_435.Solution1solution1;`
	`12`	`+privatestatic_435.Solution2solution2;`
`12`	`13`
`13`	`14`	`@BeforeClass`
`14`	`15`	`publicstaticvoidsetup() {`
`15`	`16`	`solution1 =new_435.Solution1();`
	`17`	`+solution2 =new_435.Solution2();`
`16`	`18`	`}`
`17`	`19`
`18`	`20`	`@Test`
`19`	`21`	`publicvoidtest1() {`
`20`	`22`	`int[][]intervals =CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[1,2],[2,3],[3,4],[1,3]");`
`21`	`23`	`assertEquals(1,solution1.eraseOverlapIntervals(intervals));`
	`24`	`+assertEquals(1,solution2.eraseOverlapIntervals(intervals));`
	`25`	`+ }`
	`26`	`+`
	`27`	`+@Test`
	`28`	`+publicvoidtest2() {`
	`29`	`+int[][]intervals =CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[-52,31],[-73,-26],[82,97],[-65,-11],[-62,-49],[95,99],[58,95],[-31,49],[66,98],[-63,2],[30,47],[-40,-26]");`
	`30`	`+assertEquals(7,solution1.eraseOverlapIntervals(intervals));`
	`31`	`+assertEquals(7,solution2.eraseOverlapIntervals(intervals));`
`22`	`32`	`}`
`23`	`33`
`24`	`34`	`}`

Comments

(0)