2023-07-23：給你 n 個任務和 m 個工人

每個任務需要一定的力量值才能完成

需要的力量值保存在下標從 0 開始的整數數組 tasks 中

第 i 個任務需要 tasks[i] 的力量才能完成

每個工人的力量值保存在下標從 0 開始的整數數組 workers 中

第 j 個工人的力量值為 workers[j]

每個工人只能完成 一個 任務

且力量值需要 大于等于 該任務的力量要求值, 即 workers[j] >= tasks[i]

除此以外，你還有 pills 個神奇藥丸

可以給 一個工人的力量值 增加 strength

你可以決定給哪些工人使用藥丸

但每個工人 最多 只能使用 一片 藥丸。

給你下標從 0 開始的整數數組tasks 和 workers 以及

兩個整數 pills 和 strength ，請你返回 最多 有多少個任務可以被完成。

來自華為。

輸入：tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1。

輸出：3。

答案2023-07-23：

maxTaskAssign1:

1.對任務數組 tasks 和工人數組 workers 進行升序排序。

2.使用二分查找在任務數組 tasks 中找到一個索引 m，使得從 tasks[0] 到 tasks[m-1] 的任務可以被 workers[len(workers)-m] 到 workers[len(workers)-1] 完成。

3.判斷使用藥丸后，從 tasks[m] 到 tasks[len(tasks)-1] 的剩余任務是否能夠被剩余的工人完成。

4.如果可以完成，則繼續在右半部分尋找更大的 m 值；如果無法完成，則在左半部分尋找更小的 m 值。

5.返回最終的 m 值，即最多可以完成的任務數。

maxTaskAssign2:

1.對任務數組 tasks 和工人數組 workers 進行升序排序。

2.使用二分查找在任務數組 tasks 中找到一個索引 m，使得從 tasks[0] 到 tasks[m-1] 的任務可以被 workers[len(workers)-m] 到 workers[len(workers)-1] 完成。

3.使用輔助數組 help 存儲滿足條件的任務索引。

4.從 workers[wl] 到 workers[wr] 遍歷每個工人，依次分配任務。

5.在任務數組 tasks 中，使用雙指針 l 和 r，將滿足 workers[wi] <= tasks[help[l]] <= workers[wi]+strength 的任務指針存入 help 數組。

6.如果 l < r，則說明有任務可以被工人完成，將任務數加一，并將 r 減一。

7.如果 l >= r，則說明無法完成任務，返回一個很大的值。

8.返回最終的任務數。

算法maxTaskAssign1的時間復雜度為O(n log n + m log m)，空間復雜度為O(n + m)。

算法maxTaskAssign2的時間復雜度為O((n + m) log n)，空間復雜度為O(n)。
# go完整代碼如下：

```go
package main

import (
    "fmt"
    "sort"
)

func maxTaskAssign1(tasks []int, workers []int, pills int, strength int) int {
    l := 0
    r := len(tasks)
    var m, ans int
    sort.Ints(tasks)
    sort.Ints(workers)
    for l <= r {
        m = (l + r) / 2
        if yeah1(tasks, 0, m-1, workers, len(workers)-m, len(workers)-1, strength) <= pills {
            ans = m
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return ans
}

func yeah1(tasks []int, tl int, tr int, workers []int, wl int, wr int, strength int) int {
    if wl < 0 {
        return int(^uint(0) >> 1)
    }
    taskMap := make(map[int]int)
    for i := tl; i <= tr; i++ {
        taskMap[tasks[i]]++
    }
    var ans int
    for i := wl; i <= wr; i++ {
        job := floorKey(taskMap, workers[i])
        if job != nil {
            times := taskMap[*job]
            if times == 1 {
                delete(taskMap, *job)
            } else {
                taskMap[*job]--
            }
        } else {
            job = floorKey(taskMap, workers[i]+strength)
            if job == nil {
                return int(^uint(0) >> 1)
            }
            ans++
            times := taskMap[*job]
            if times == 1 {
                delete(taskMap, *job)
            } else {
                taskMap[*job]--
            }
        }
    }
    return ans
}

func floorKey(taskMap map[int]int, key int) *int {
    floorKey := -1
    for k := range taskMap {
        if k > floorKey && k <= key {
            floorKey = k
        }
    }
    if floorKey == -1 {
        return nil
    }
    return &floorKey
}

func maxTaskAssign2(tasks []int, workers []int, pills int, strength int) int {
    help := make([]int, len(tasks))
    l := 0
    r := len(tasks)
    var m, ans int
    sort.Ints(tasks)
    sort.Ints(workers)
    for l <= r {
        m = (l + r) / 2
        if yeah2(tasks, 0, m-1, workers, len(workers)-m, len(workers)-1, strength, help) <= pills {
            ans = m
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return ans
}

func yeah2(tasks []int, tl int, tr int, workers []int, wl int, wr int, strength int, help []int) int {
    if wl < 0 {
        return int(^uint(0) >> 1)
    }
    l := 0
    r := 0
    ti := tl
    var ans int
    for wi := wl; wi <= wr; wi++ {
        for ; ti <= tr && tasks[ti] <= workers[wi]; ti++ {
            help[r] = ti
            r++
        }
        if l < r && tasks[help[l]] <= workers[wi] {
            l++
        } else {
            for ; ti <= tr && tasks[ti] <= workers[wi]+strength; ti++ {
                help[r] = ti
                r++
            }
            if l < r {
                ans++
                r--
            } else {
                return int(^uint(0) >> 1)
            }
        }
    }
    return ans
}

func main() {
    tasks := []int{3, 2, 1}
    workers := []int{0, 3, 3}
    pills := 1
    strength := 1

    fmt.Println("maxTaskAssign1:", maxTaskAssign1(tasks, workers, pills, strength))
    fmt.Println("maxTaskAssign2:", maxTaskAssign2(tasks, workers, pills, strength))
}
```


# rust完整代碼如下：

```rust
use std::collections::BTreeMap;

fn max_task_assign1(tasks: Vec<i32>, workers: Vec<i32>, pills: i32, strength: i32) -> i32 {
    let mut l = 0;
    let mut r = tasks.len();
    let mut ans = 0;
    let mut sorted_tasks = tasks.clone();
    sorted_tasks.sort();
    let mut sorted_workers = workers.clone();
    sorted_workers.sort();

    while l <= r {
        let m = (l + r) / 2;
        if yeah1(
            &sorted_tasks,
            0,
            m - 1,
            &sorted_workers,
            workers.len() - m,
            workers.len() - 1,
            strength,
        ) <= pills
        {
            ans = m as i32;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    ans
}

fn yeah1(
    tasks: &[i32],
    tl: usize,
    tr: usize,
    workers: &[i32],
    wl: usize,
    wr: usize,
    strength: i32,
) -> i32 {
    if wl >= workers.len() {
        return i32::max_value();
    }

    let mut task_map = BTreeMap::new();
    for i in tl..=tr {
        *task_map.entry(tasks[i]).or_insert(0) += 1;
    }

    let mut ans = 0;
    for i in wl..=wr {
        let job = match task_map.range(..=workers[i]).rev().next() {
            Some((key, _)) => *key,
            None => {
                let job = match task_map.range(..=(workers[i] + strength)).rev().next() {
                    Some((key, _)) => *key,
                    None => return i32::max_value(),
                };
                ans += 1;
                job
            }
        };
        let times = task_map.get(&job).cloned().unwrap();
        if times == 1 {
            task_map.remove(&job);
        } else {
            task_map.insert(job, times - 1);
        }
    }

    ans
}

fn max_task_assign2(tasks: Vec<i32>, workers: Vec<i32>, pills: i32, strength: i32) -> i32 {
    let mut help = vec![0; tasks.len()];
    let mut l = 0;
    let mut r = tasks.len();
    let mut ans = 0;
    let mut sorted_tasks = tasks.clone();
    sorted_tasks.sort();
    let mut sorted_workers = workers.clone();
    sorted_workers.sort();

    while l <= r {
        let m = (l + r) / 2;
        if yeah2(
            &sorted_tasks,
            0,
            m - 1,
            &sorted_workers,
            workers.len() - m,
            workers.len() - 1,
            strength,
            &mut help,
        ) <= pills
        {
            ans = m as i32;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    ans
}

fn yeah2(
    tasks: &[i32],
    tl: usize,
    tr: usize,
    workers: &[i32],
    wl: usize,
    wr: usize,
    strength: i32,
    help: &mut [i32],
) -> i32 {
    if wl >= workers.len() {
        return i32::max_value();
    }

    let mut l = 0;
    let mut r = 0;
    let mut ti = tl;
    let mut ans = 0;

    for wi in wl..=wr {
        while ti <= tr && tasks[ti] <= workers[wi] {
            help[r] = ti as i32;
            r += 1;
            ti += 1;
        }

        if l < r && tasks[help[l as usize] as usize] <= workers[wi] {
            l += 1;
        } else {
            while ti <= tr && tasks[ti] <= workers[wi] + strength {
                help[r] = ti as i32;
                r += 1;
                ti += 1;
            }

            if l < r {
                ans += 1;
                r -= 1;
            } else {
                return i32::max_value();
            }
        }
    }

    ans
}

fn main() {
    let tasks = vec![3, 2, 1];
    let workers = vec![0, 3, 3];
    let pills = 1;
    let strength = 1;

    let result1 = max_task_assign1(tasks.clone(), workers.clone(), pills, strength);
    let result2 = max_task_assign2(tasks, workers, pills, strength);

    println!("max_task_assign1 result: {}", result1);
    println!("max_task_assign2 result: {}", result2);
}

```


# c++代碼如下：

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int yeah1(vector<int>& tasks, int tl, int tr, vector<int>& workers, int wl, int wr, int strength) {
    if (wl < 0) {
        return INT_MAX;
    }
    map<int, int> taskMap;
    for (int i = tl; i <= tr; i++) {
        taskMap[tasks[i]]++;
    }
    int ans = 0;
    for (int i = wl; i <= wr; i++) {
        auto job = taskMap.lower_bound(workers[i]);
        if (job != taskMap.end()) {
            int times = job->second;
            if (times == 1) {
                taskMap.erase(job);
            }
            else {
                job->second--;
            }
        }
        else {
            job = taskMap.lower_bound(workers[i] + strength);
            if (job == taskMap.end()) {
                return INT_MAX;
            }
            ans++;
            int times = job->second;
            if (times == 1) {
                taskMap.erase(job);
            }
            else {
                job->second--;
            }
        }
    }
    return ans;
}

int maxTaskAssign1(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
    int l = 0;
    int r = tasks.size();
    int m, ans = 0;
    sort(tasks.begin(), tasks.end());
    sort(workers.begin(), workers.end());
    while (l <= r) {
        m = (l + r) / 2;
        if (yeah1(tasks, 0, m - 1, workers, workers.size() - m, workers.size() - 1, strength) <= pills) {
            ans = m;
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }
    return ans;
}

int yeah2(vector<int>& tasks, int tl, int tr, vector<int>& workers, int wl, int wr, int strength, vector<int>& help) {
    if (wl < 0) {
        return INT_MAX;
    }
    int l = 0;
    int r = 0;
    int ti = tl;
    int ans = 0;
    for (int wi = wl; wi <= wr; wi++) {
        for (; ti <= tr && tasks[ti] <= workers[wi]; ti++) {
            help[r++] = ti;
        }
        if (l < r && tasks[help[l]] <= workers[wi]) {
            l++;
        }
        else {
            for (; ti <= tr && tasks[ti] <= workers[wi] + strength; ti++) {
                help[r++] = ti;
            }
            if (l < r) {
                ans++;
                r--;
            }
            else {
                return INT_MAX;
            }
        }
    }
    return ans;
}

int maxTaskAssign2(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
    vector<int> help(tasks.size());
    int l = 0;
    int r = tasks.size();
    int m, ans = 0;
    sort(tasks.begin(), tasks.end());
    sort(workers.begin(), workers.end());
    while (l <= r) {
        m = (l + r) / 2;
        if (yeah2(tasks, 0, m - 1, workers, workers.size() - m, workers.size() - 1, strength, help) <= pills) {
            ans = m;
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }
    return ans;
}

int main() {
    vector<int> tasks = { 3, 2, 1 };
    vector<int> workers = { 0, 3, 3 };
    int pills = 1;
    int strength = 1;

    //int result1 = maxTaskAssign1(tasks, workers, pills, strength);
    int result2 = maxTaskAssign2(tasks, workers, pills, strength);

    //cout << "Result from maxTaskAssign1: " << result1 << endl;
    cout << "Result from maxTaskAssign2: " << result2 << endl;

    return 0;
}
```


# c完整代碼如下：

```c
#include <stdio.h>
#include <stdlib.h>

int yeah1(int* tasks, int tl, int tr, int* workers, int wl, int wr, int strength) {
    if (wl < 0) {
        return INT_MAX;
    }
    int taskMap[1001] = { 0 };

    for (int i = tl; i <= tr; i++) {
        taskMap[tasks[i]]++;
    }

    int ans = 0;

    for (int i = wl; i <= wr; i++) {
        int job = -1;

        for (int j = workers[i]; j >= 0; j--) {
            if (taskMap[j] > 0) {
                job = j;
                break;
            }
        }

        if (job != -1) {
            taskMap[job]--;
        }
        else {
            job = -1;

            for (int j = workers[i] + strength; j >= workers[i]; j--) {
                if (taskMap[j] > 0) {
                    job = j;
                    break;
                }
            }

            if (job == -1) {
                return INT_MAX;
            }

            ans++;
            taskMap[job]--;
        }
    }

    return ans;
}

int compare(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int maxTaskAssign1(int* tasks, int tasksSize, int* workers, int workersSize, int pills, int strength) {
    int l = 0;
    int r = tasksSize;
    int m, ans = 0;
    int* sortedTasks = (int*)malloc(tasksSize * sizeof(int));
    int* sortedWorkers = (int*)malloc(workersSize * sizeof(int));

    for (int i = 0; i < tasksSize; i++) {
        sortedTasks[i] = tasks[i];
    }

    for (int i = 0; i < workersSize; i++) {
        sortedWorkers[i] = workers[i];
    }

    qsort(sortedTasks, tasksSize, sizeof(int), compare);
    qsort(sortedWorkers, workersSize, sizeof(int), compare);

    while (l <= r) {
        m = (l + r) / 2;

        if (yeah1(sortedTasks, 0, m - 1, sortedWorkers, workersSize - m, workersSize - 1, strength) <= pills) {
            ans = m;
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }

    free(sortedTasks);
    free(sortedWorkers);

    return ans;
}

int yeah2(int* tasks, int tl, int tr, int* workers, int wl, int wr, int strength, int* help) {
    if (wl < 0) {
        return INT_MAX;
    }

    int l = 0;
    int r = 0;
    int ti = tl;
    int ans = 0;

    for (int wi = wl; wi <= wr; wi++) {
        for (; ti <= tr && tasks[ti] <= workers[wi]; ti++) {
            help[r++] = ti;
        }

        if (l < r && tasks[help[l]] <= workers[wi]) {
            l++;
        }
        else {
            for (; ti <= tr && tasks[ti] <= workers[wi] + strength; ti++) {
                help[r++] = ti;
            }

            if (l < r) {
                ans++;
                r--;
            }
            else {
                return INT_MAX;
            }
        }
    }

    return ans;
}

int maxTaskAssign2(int* tasks, int tasksSize, int* workers, int workersSize, int pills, int strength) {
    int* help = (int*)malloc(tasksSize * sizeof(int));
    int l = 0;
    int r = tasksSize;
    int m, ans = 0;
    int* sortedTasks = (int*)malloc(tasksSize * sizeof(int));
    int* sortedWorkers = (int*)malloc(workersSize * sizeof(int));

    for (int i = 0; i < tasksSize; i++) {
        sortedTasks[i] = tasks[i];
    }

    for (int i = 0; i < workersSize; i++) {
        sortedWorkers[i] = workers[i];
    }

    qsort(sortedTasks, tasksSize, sizeof(int), compare);
    qsort(sortedWorkers, workersSize, sizeof(int), compare);

    while (l <= r) {
        m = (l + r) / 2;

        if (yeah2(sortedTasks, 0, m - 1, sortedWorkers, workersSize - m, workersSize - 1, strength, help) <= pills) {
            ans = m;
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }

    free(help);
    free(sortedTasks);
    free(sortedWorkers);

    return ans;
}

int main() {
    int tasks[] = { 3, 2, 1 };
    int tasksSize = sizeof(tasks) / sizeof(tasks[0]);
    int workers[] = { 0, 3, 3 };
    int workersSize = sizeof(workers) / sizeof(workers[0]);
    int pills = 1;
    int strength = 1;

    int max1 = maxTaskAssign1(tasks, tasksSize, workers, workersSize, pills, strength);
    int max2 = maxTaskAssign2(tasks, tasksSize, workers, workersSize, pills, strength);

    printf("maxTaskAssign1: %d\n", max1);
    printf("maxTaskAssign2: %d\n", max2);

    return 0;
}
```