Commit562333a

authored

Create 0646-maximum-length-of-pair-chain.kt

1 parentd164ce1 commit562333aCopy full SHA for 562333a

File tree

+36

-0

lines changed

+36

-0

lines changed

Lines changed: 36 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,36 @@`
	`1`	`+//greedy algorithm O(nlogn)`
	`2`	`+classSolution {`
	`3`	`+funfindLongestChain(_pairs:Array<IntArray>):Int {`
	`4`	`+val pairs=_pairs.sortedWith(compareBy({ it[1] }, { it[0] }))`
	`5`	`+`
	`6`	`+var res=1`
	`7`	`+var time= pairs[0][1]`
	`8`	`+for (iin1 until pairs.size) {`
	`9`	`+if(pairs[i][0]> time) {`
	`10`	`+ res++`
	`11`	`+ time= pairs[i][1]`
	`12`	`+ }`
	`13`	`+ }`
	`14`	`+`
	`15`	`+return res`
	`16`	`+ }`
	`17`	`+}`
	`18`	`+`
	`19`	`+//dp O(n^2)`
	`20`	`+classSolution {`
	`21`	`+funfindLongestChain(_pairs:Array<IntArray>):Int {`
	`22`	`+val pairs=_pairs.sortedWith(compareBy({ it[0] }, { it[1] }))`
	`23`	`+val n= pairs.size`
	`24`	`+val dp=IntArray(n) {1 }`
	`25`	`+`
	`26`	`+for (iin0 until n) {`
	`27`	`+for (jin0 until n) {`
	`28`	`+if (pairs[i][0]> pairs[j][1]) {`
	`29`	`+ dp[i]= maxOf(dp[i], dp[j]+1)`
	`30`	`+ }`
	`31`	`+ }`
	`32`	`+ }`
	`33`	`+`
	`34`	`+return dp[n-1]`
	`35`	`+ }`
	`36`	`+}`

Comments

(0)