[LeetCode]Most Profit Assigning Work

这道题相同的task允许取多次，所以本质上就是对于一个worker来说，我们要找difficulty在[0, x]之间的最大profit，x为小于等于worker能承受范围的最大值。那么我们可以维护一个sorted的序列，按照task的difficulty从小到大排序，break tie by profit从小到大。那么对于每一个task 的difficulty di，我们用一个array a[]存小于等于di的task中的最大profit a[i]，我们从左到右扫一次就可以构建好a。之后对于每一个worker，我们在a中binary search找到difficulty小于worker[i]的最大值对应的值，这就是worker[i]所能达到的最大profit。我们对每一个worker都重复这个操作即可。假设有n个task，m个worker，时间复杂度为O(n * log n + m * log n)，空间复杂度O(n)。代码如下：


另一种放方法，如果worker的array是sorted的话，我们要在a中找的对应的元素也是单调递增的，所以双指针就完全可以解决这个问题。同时因为我们是从左向右扫的，只需要用一个变量维护遇到过的最大profit就可以了，也就是说a数组我们也不需要了。时间复杂度O(m + n + m * log m + n * log n)，空间复杂度O(n)，代码如下：