FastPrep
Problem · Math

Job Scheduling

Learn this problem
● MediumSofiFULLTIMEOA

Problem statement

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 kth 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 kth processor, such that the overall schedule remains balanced.

Note: Each processor must have at least one job scheduled.

Function

getMaximumJobs(n: int, m: int, k: int) → int

Complete the function getMaximumJobs in the editor.

getMaximumJobs has the following parameters:

  1. int n: the number of processors
  2. int m: the number of jobs
  3. int k: the 1-based index of the most efficient processor

Returns

int: the maximum number of jobs that can be scheduled on the kth processor maintaining a balanced schedule

Examples

Example 1

n = 5m = 11k = 5return = 4

Given n = 5, m = 11, k = 5.

One optimal job schedule is [1, 1, 2, 3, 4].

Example 2

n = 5m = 11k = 3return = 3
Example 2 illustration
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 :)

Constraints

  • 1 ≤ n ≤ 105
  • n ≤ m ≤ 109
  • 1 ≤ k ≤ n

More Sofi problems

drafts saved locally
public int getMaximumJobs(int n, int m, int k) {
  // write your code here
}
n5
m11
k5
expected4
checking account