Skip to content

2071. Maximum Number of Tasks You Can Assign 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
 public:
  int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills,
                    int strength) {
    int ans = 0;
    int l = 0;
    int r = min(tasks.size(), workers.size());

    ranges::sort(tasks);
    ranges::sort(workers);

    // Returns true if we can finish k tasks.
    auto canComplete = [&](int k, int pillsLeft) {
      // k strongest workers
      map<int, int> sortedWorkers;
      for (int i = workers.size() - k; i < workers.size(); ++i)
        ++sortedWorkers[workers[i]];

      // Out of the k smallest tasks, start from the biggest one.
      for (int i = k - 1; i >= 0; --i) {
        // Find the first worker that has strength >= tasks[i].
        auto it = sortedWorkers.lower_bound(tasks[i]);
        if (it != sortedWorkers.end()) {
          if (--(it->second) == 0)
            sortedWorkers.erase(it);
        } else if (pillsLeft > 0) {
          // Find the first worker that has strength >= tasks[i] - strength.
          it = sortedWorkers.lower_bound(tasks[i] - strength);
          if (it != sortedWorkers.end()) {
            if (--(it->second) == 0)
              sortedWorkers.erase(it);
            --pillsLeft;
          } else {
            return false;
          }
        } else {
          return false;
        }
      }

      return true;
    };

    while (l <= r) {
      const int m = (l + r) / 2;
      if (canComplete(m, pills)) {
        ans = m;
        l = m + 1;
      } else {
        r = m - 1;
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
  public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
    int ans = 0;
    int l = 0;
    int r = Math.min(tasks.length, workers.length);

    Arrays.sort(tasks);
    Arrays.sort(workers);

    while (l <= r) {
      final int m = (l + r) / 2;
      if (canComplete(tasks, workers, pills, strength, m)) {
        ans = m;
        l = m + 1;

      } else {
        r = m - 1;
      }
    }

    return ans;
  }

  // Returns true if we can finish k tasks.
  private boolean canComplete(int[] tasks, int[] workers, int pillsLeft, int strength, int k) {
    // k strongest workers
    TreeMap<Integer, Integer> sortedWorkers = new TreeMap<>();
    for (int i = workers.length - k; i < workers.length; ++i)
      sortedWorkers.merge(workers[i], 1, Integer::sum);

    // Out of the k smallest tasks, start from the biggest one.
    for (int i = k - 1; i >= 0; --i) {
      // Find the first worker that has strength >= tasks[i].
      Integer lo = sortedWorkers.ceilingKey(tasks[i]);
      if (lo != null) {
        sortedWorkers.merge(lo, -1, Integer::sum);
        if (sortedWorkers.get(lo) == 0) {
          sortedWorkers.remove(lo);
        }
      } else if (pillsLeft > 0) {
        // Find the first worker that has strength >= tasks[i] - strength.
        lo = sortedWorkers.ceilingKey(tasks[i] - strength);
        if (lo != null) {
          sortedWorkers.merge(lo, -1, Integer::sum);
          if (sortedWorkers.get(lo) == 0) {
            sortedWorkers.remove(lo);
          }
          --pillsLeft;
        } else {
          return false;
        }
      } else {
        return false;
      }
    }

    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from sortedcontainers import SortedList


class Solution:
  def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
    tasks.sort()
    workers.sort()

    def canComplete(k: int, pillsLeft: int) -> bool:
      """Returns True if we can finish k tasks."""
      # k strongest workers
      sortedWorkers = SortedList(workers[-k:])

      # Out of the k smallest tasks, start from the biggest one.
      for i in reversed(range(k)):
        # Find the first worker that has strength >= tasks[i].
        index = sortedWorkers.bisect_left(tasks[i])
        if index < len(sortedWorkers):
          sortedWorkers.pop(index)
        elif pillsLeft > 0:
          # Find the first worker that has strength >= tasks[i] - strength.
          index = sortedWorkers.bisect_left(tasks[i] - strength)
          if index < len(sortedWorkers):
            sortedWorkers.pop(index)
            pillsLeft -= 1
          else:
            return False
        else:
          return False

      return True

    ans = 0
    l = 0
    r = min(len(tasks), len(workers))

    while l <= r:
      m = (l + r) // 2
      if canComplete(m, pills):
        ans = m
        l = m + 1
      else:
        r = m - 1

    return ans