[Swift]LeetCode826.安排工作以达到最大收益|MostProfitAssigningWork

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10569392.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job.

Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i].

Every worker can be assigned at most one job, but one job can be completed multiple times.

For example, if 3 people attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, his profit is $0.

What is the most profit we can make?

Example 1:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100 
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get profit of [20,20,30,30] seperately.

Notes:

1 <= difficulty.length = profit.length <= 10000
1 <= worker.length <= 10000
difficulty[i], profit[i], worker[i] are in range [1, 10^5]

有一些工作：difficulty[i] 表示第i个工作的难度，profit[i]表示第i个工作的收益。

现在我们有一些工人。worker[i]是第i个工人的能力，即该工人只能完成难度小于等于worker[i]的工作。

每一个工人都最多只能安排一个工作，但是一个工作可以完成多次。

举个例子，如果3个工人都尝试完成一份报酬为1的同样工作，那么总收益为 $3。如果一个工人不能完成任何工作，他的收益为 $0 。

我们能得到的最大收益是多少？

示例：

输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100 
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。

提示:

1 <= difficulty.length = profit.length <= 10000
1 <= worker.length <= 10000
difficulty[i], profit[i], worker[i] 的范围是 [1, 10^5]

580ms

 1 class Solution {
 2     func maxProfitAssignment(_ difficulty: [Int], _ profit: [Int], _ worker: [Int]) -> Int {
 3         var tasks = [(Int, Int)]()
 4         for i in 0..<difficulty.count {
 5             tasks.append((profit[i], difficulty[i]))
 6         }
 7         tasks = tasks.sorted {$0.0 > $1.0}
 8         var workers = worker.sorted {$0 > $1}
 9         var t = 0, w = 0
10         var res = 0
11         while (w < worker.count && t < tasks.count) {
12             if tasks[t].1 <= workers[w] {
13                 res += tasks[t].0
14                 w += 1
15             } else {
16                 t += 1
17             }
18         }
19         return res
20     }
21 }

588ms

 1 class Solution {    
 2     func maxProfitAssignment(_ difficulty: [Int], _ profit: [Int], _ worker: [Int]) -> Int {
 3         let dp = zip(difficulty, profit).sorted(by: {$0.0 < $1.0})
 4         
 5         var p = 0
 6         var i = 0, maxp = 0
 7         for w in worker.sorted(by: <) {
 8             while i < dp.count && w >= dp[i].0 {
 9                 maxp = max(maxp, dp[i].1)
10                 i += 1
11             }
12             p += maxp
13         }        
14         return p
15     }
16 }

616ms

 1 class Solution {
 2     func maxProfitAssignment(_ difficulty: [Int], _ profit: [Int], _ worker: [Int]) -> Int {
 3         var dp = [Int : Int]()
 4         for i in 0..<difficulty.count {
 5             let d = difficulty[i]
 6             let p = profit[i]
 7             if dp[d, default: 0] < p {
 8                 dp[d] = p
 9             }
10         }
11         let keys = dp.keys.sorted()
12         var maxSoFar = 0
13         var sanitizedD = [Int]()
14         var sanitizedP = [Int]()
15         for i in 0..<keys.count {
16             let key = keys[i]
17             if dp[key]! > maxSoFar {
18                 maxSoFar = dp[key]!
19                 sanitizedD.append(key)
20                 sanitizedP.append(dp[key]!)
21             }
22         }
23 
24         var result = 0
25         for i in 0..<worker.count {
26             let w = worker[i]
27             result += maxFittingProfit(forWorker: w, inDifficulties: sanitizedD, withProfits:sanitizedP)
28         }
29         
30         return result
31     }
32     
33     func maxFittingProfit(forWorker worker: Int, inDifficulties difficulties: [Int], withProfits profits: [Int]) -> Int
34     {
35         var lower = 0, upper = difficulties.count - 1
36         var i = profits.count / 2
37         while (lower <= upper) {
38             if difficulties[i] > worker {
39                 upper = i - 1
40                 i = (lower + upper) / 2
41             }
42             else if (i != difficulties.count - 1) && (difficulties[i+1] <= worker) {
43                 lower = i + 1
44                 i = (lower + upper) / 2
45             }
46             else {
47                 return profits[i]
48             }
49         }
50         return 0
51     }
52 }

620ms

 1 class Solution {
 2     func binarySearch(_ difficulty: inout [Int], _ worker: Int) -> Int? {
 3         if difficulty.count == 0 || difficulty[0] > worker {
 4             return nil
 5         }
 6         
 7         var left = 0, right = difficulty.count - 1
 8         while left < right {
 9             let mid = left + (right - left) / 2
10             if worker >= difficulty[mid] &&
11                 worker < difficulty[mid + 1] {
12                 return mid
13             }
14             
15             if worker > difficulty[mid] {
16                 left = mid + 1
17             } else {
18                 right = mid
19             }
20         }
21         
22         return left
23     }
24     
25     func maxProfitAssignment(_ difficulty: [Int], _ profit: [Int], _ worker: [Int]) -> Int {
26         var p = 0
27         
28         let ed = difficulty.enumerated().sorted(by: { $0.element < $1.element })
29         var dp = [Int: Int]()
30         var maxp = 0
31         for (index, d) in ed {
32             maxp = max(maxp, profit[index])
33             dp[d] = maxp
34         }
35 
36         var d = difficulty.sorted()
37         for w in worker {
38             let di = binarySearch(&d, w)
39             if let di = di {
40                 p += dp[d[di]]!
41             }
42         }        
43         return p
44     }
45 }

628ms

 1 class Solution {
 2     func maxProfitAssignment(_ difficulty: [Int], _ profit: [Int], _ worker: [Int]) -> Int {
 3         var jobs = [Int: Int]() // [Difficulty, Profit]
 4         for i in 0..<difficulty.count {
 5             let d = difficulty[i]
 6             if let existing = jobs[d] {
 7                 jobs[d] = max(existing, profit[i])
 8             } else {
 9                 jobs[d] = profit[i]
10             }
11         }
12         let sorted = jobs.sorted { (a, b) -> Bool in
13             if a.value == b.value {
14                 return a.key > b.key
15             } else {
16                 return a.value > b.value
17             }
18         }
19         var current = 0        
20         let worker = worker.sorted().reversed()        
21         var maxProfit = 0
22         
23         for w in worker {
24             while current < sorted.count, sorted[current].key > w {
25                 current += 1
26             }
27             
28             if current == sorted.count {
29                 return maxProfit
30             } else {
31                 maxProfit += sorted[current].value
32             }
33         }        
34         return maxProfit
35     }
36 }

Runtime: 668 ms

Memory Usage: 20.1 MB

 1 class Solution {
 2     func maxProfitAssignment(_ difficulty: [Int], _ profit: [Int], _ worker: [Int]) -> Int {
 3         var res:Int = 0
 4         var n:Int = profit.count
 5         var dp:[Int] = [Int](repeating:0,count:100001)
 6         for i in 0..<n
 7         {
 8             dp[difficulty[i]] = max(dp[difficulty[i]], profit[i])
 9         }
10         for i in 1..<dp.count
11         {
12             dp[i] = max(dp[i], dp[i - 1])
13         }
14         for ability in worker
15         {
16             res += dp[ability]
17         }
18         return res
19     }
20 }

772ms

 1 class Solution {
 2     func maxProfitAssignment(_ difficulty: [Int], _ profit: [Int], _ worker: [Int]) -> Int {
 3         var max = 0 as Int        
 4         let count = difficulty.count
 5 
 6         var sortedCache = [[Int]:Int]()
 7         for i in 0...count-1{
 8             sortedCache[[difficulty[i],i]] = profit[i]
 9         }
10         
11         var difficulty_ = sortedCache.keys.sorted{
12             return $0[0] < $1[0]
13         }
14         
15         var maxProfitCache = [Int:Int]()
16         var sortedMPKeys = [Int]()        
17         var runningMaxProfit = 0
18         
19         for i in 0...count-1{
20             
21             let nextK = difficulty_[i]
22             let dif = nextK[0]
23             var profit = sortedCache[nextK] as! Int
24         
25             var nextMax = maxProfitCache[dif] ?? 0
26             let nextMax_ = nextMax
27             
28             if runningMaxProfit > profit{
29                 profit = runningMaxProfit    
30             }
31             
32             if profit > nextMax{
33                 
34                 runningMaxProfit = profit
35                 nextMax = profit
36                 maxProfitCache[dif] = nextMax
37                 
38                 if nextMax_ == 0{
39                     sortedMPKeys.append(dif)
40                 }
41             }                
42         }
43         
44         sortedMPKeys = sortedMPKeys.sorted()
45         
46         for w in worker{
47             var maxW = 0 as Int
48             let index = binarySearch(sortedMPKeys, key: w, range: 0 ..< sortedMPKeys.count)
49             if index != nil && index! >= 0{
50                 maxW = maxProfitCache[sortedMPKeys[index!]]!
51             }else if index == nil && index != -1{
52                 maxW = maxProfitCache[sortedMPKeys.last!]!
53             }
54 
55             max += maxW
56         }
57         return max
58     }
59 }
60 
61 func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
62     return _binarySearch(a, key: key, range: range, -1)
63 }
64 
65 func _binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>, _ maxIdxResult : Int) -> Int? {
66     
67     var maxIdxResult = maxIdxResult
68     
69     if range.lowerBound >= range.upperBound {
70         return maxIdxResult
71 
72     } else {
73         let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
74         if a[midIndex] > key {
75             return _binarySearch(a, key: key, range: range.lowerBound ..< midIndex,maxIdxResult)
76         } else if a[midIndex] < key {
77             maxIdxResult = midIndex
78             return _binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound,maxIdxResult)
79         } else {
80             return midIndex
81         }
82     }
83 }
84 
85 func println(_ format : String, _ args : CVarArg...) {
86     let s = String.init(format: format, arguments: args)
87     print(s, separator: "", terminator: "\n")
88 }