|
| 1 | +// Recursion + Memoization |
1 | 2 | classSolution { |
2 | 3 | funjobScheduling(s:IntArray,e:IntArray,p:IntArray):Int { |
3 | 4 | val dp=IntArray (s.size) {-1 } |
@@ -35,3 +36,72 @@ class Solution { |
35 | 36 | return dfs(0) |
36 | 37 | } |
37 | 38 | } |
| 39 | + |
| 40 | +// Top-down DP |
| 41 | +classSolution { |
| 42 | +funjobScheduling(sT:IntArray,eT:IntArray,p:IntArray):Int { |
| 43 | +val jobs= sT.indices |
| 44 | + .map { intArrayOf(sT[it], eT[it], p[it]) } |
| 45 | + .sortedWith(compareBy({ it[0] }, { it[1] })) |
| 46 | + |
| 47 | +val n= jobs.size |
| 48 | +val last= n-1 |
| 49 | +val dp=IntArray (n) |
| 50 | + |
| 51 | +for (iin last downTo0) { |
| 52 | +var j=-1 |
| 53 | +var l= i |
| 54 | +var r= last |
| 55 | +while (l<= r) { |
| 56 | +val m= (l+ r)/2 |
| 57 | +if (jobs[m][0]>= jobs[i][1]) { |
| 58 | + j= m |
| 59 | + r= m-1 |
| 60 | + }else { |
| 61 | + l= m+1 |
| 62 | + } |
| 63 | + } |
| 64 | + |
| 65 | + dp[i]= maxOf( |
| 66 | + jobs[i][2]+ (if (j!=-1) dp[j]else0), |
| 67 | +if (i+1< n) dp[i+1]else0 |
| 68 | + ) |
| 69 | + } |
| 70 | + |
| 71 | +return dp[0] |
| 72 | + } |
| 73 | +} |
| 74 | + |
| 75 | +//Bottom-up DP |
| 76 | +classSolution { |
| 77 | +funjobScheduling(sT:IntArray,eT:IntArray,p:IntArray):Int { |
| 78 | +val jobs= sT.indices |
| 79 | + .map { intArrayOf(sT[it], eT[it], p[it]) } |
| 80 | + .sortedWith(compareBy({ it[1] }, { it[0] })) |
| 81 | + |
| 82 | +val n= jobs.size |
| 83 | +val dp=IntArray (n) |
| 84 | + |
| 85 | +for (iin0 until n) { |
| 86 | +var l=0 |
| 87 | +var r= i-1 |
| 88 | +var j=-1 |
| 89 | +while (l<= r) { |
| 90 | +val m= (l+ r)/2 |
| 91 | +if (jobs[m][1]<= jobs[i][0]) { |
| 92 | + j= m |
| 93 | + l= m+1 |
| 94 | + }else { |
| 95 | + r= m-1 |
| 96 | + } |
| 97 | + } |
| 98 | + |
| 99 | + dp[i]= maxOf( |
| 100 | + jobs[i][2]+if (j>=0) dp[j]else0, |
| 101 | +if (i-1>=0) dp[i-1]else0 |
| 102 | + ) |
| 103 | + } |
| 104 | + |
| 105 | +return dp[n-1] |
| 106 | + } |
| 107 | +} |