Sofi | OAMaster

01Job Scheduling

There are m jobs to schedule on n processors. A schedule is balanced if the difference between the number of jobs scheduled on any two neighboring processors does not exceed 1. The k^th processor is the most efficient, and thus, the maximum number of jobs should be scheduled on that processor. Find the maximum number of jobs that can be scheduled on the k^th processor, such that the overall schedule remains balanced. Note: Each processor must have at least one job scheduled. Function Description Complete the function getMaximumJobs in the editor. getMaximumJobs has the following parameters:

int n: the number of processors
int m: the number of jobs
int k: the 1-based index of the most efficient processor Returns int: the maximum number of jobs that can be scheduled on the k^th processor maintaining a balanced schedule

Constraints

1 ≤ n ≤ 10⁵
n ≤ m ≤ 10⁹
1 ≤ k ≤ n

Example 1

Input:

n = 5
m = 11
k = 5

Output:

Explanation: Given n = 5, m = 11, k = 5. One optimal job schedule is [1, 1, 2, 3, 4].

Example 2

Input:

n = 5
m = 11
k = 3

Output:

Explanation: In each schedule, there are 11 jobs across 5 processors, k assumes 1-based indexing :) The 1st schedule is not balanced as the 5th procesor has 1 job scheduled, while th 4th processor has 4 jobs scheduled, their difference is 3, which exceeds 1 T^T The 5th schedule is not balanced as the difference between the 2nd and 3rd, and between 3rd and 4th processors is more than 1. Amongst all balanced schedules, the maximum number of jobs that can be scheduled on the 3rd processor is 3, so ther answer is 3 :)

解法

二分答案：假设第 k 号处理器分配了 x 个任务，那么左右两边沿 1 递减直到 1，再保持 1。在固定 x 下能计算最少所需总任务数 need(x)；最大的 x 使 need(x) ≤ m 即为答案。二分搜索 x ∈ [1, m]，每次 O(1) 计算 need。时间 O(log m)，空间 O(1)。

def getMaximumJobs(n: int, m: int, k: int) -> int:
    # left side has (k-1) processors with values x-1, x-2, ..., bottomed at 1
    # right side has (n-k) processors similarly
    def need(x: int) -> int:
        def side(cnt: int, peak: int) -> int:
            # cnt processors, values peak-1, peak-2, ..., flattened at 1
            if cnt == 0:
                return 0
            full = min(cnt, peak - 1)
            # sum of (peak-1) + (peak-2) + ... down to (peak-full)
            s = (peak - 1 + peak - full) * full // 2
            s += max(0, cnt - full)
            return s
        return x + side(k - 1, x) + side(n - k, x)

    lo, hi, ans = 1, m, 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if need(mid) <= m:
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

class Solution {
    int getMaximumJobs(int n, int m, int k) {
        long lo = 1, hi = m, ans = 1;
        while (lo <= hi) {
            long mid = (lo + hi) >>> 1;
            if (need(mid, n, k) <= m) { ans = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        return (int) ans;
    }
    private long need(long x, int n, int k) {
        return x + side(k - 1, x) + side(n - k, x);
    }
    private long side(int cnt, long peak) {
        if (cnt == 0) return 0;
        long full = Math.min(cnt, peak - 1);
        long s = (peak - 1 + peak - full) * full / 2;
        s += Math.max(0, cnt - full);
        return s;
    }
}

#include <algorithm>

class Solution {
    long long side(int cnt, long long peak) {
        if (cnt == 0) return 0;
        long long full = std::min((long long)cnt, peak - 1);
        long long s = (peak - 1 + peak - full) * full / 2;
        s += std::max(0LL, (long long)cnt - full);
        return s;
    }
    long long need(long long x, int n, int k) {
        return x + side(k - 1, x) + side(n - k, x);
    }
public:
    int getMaximumJobs(int n, int m, int k) {
        long long lo = 1, hi = m, ans = 1;
        while (lo <= hi) {
            long long mid = (lo + hi) / 2;
            if (need(mid, n, k) <= m) { ans = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        return (int) ans;
    }
};