FastPrep

Description

Solutions

Job Scheduling

🔥 FULLTIME📚RELATED PROBLEMS

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

Example 1:

Input:  n = 5, m = 11, k = 5
Output: 4 
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: 3 
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 :)

Constraints:

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