FastPrepMinimize the Maximum Pages Allocated
Problem · Array

Minimize the Maximum Pages Allocated

Learn this problem
● MediumGoogle logoGoogleINTERNPHONE SCREEN
See Google hiring insights

Problem statement

You are given an integer array pages, where pages[i] is the number of pages in the i-th book. The books are arranged in their original order.

Allocate every book to exactly students students under these rules:

  • Each student must receive at least one book.
  • Each student receives one contiguous segment of books.
  • The order of the books cannot change.

The load of a student is the total number of pages in that student's segment. Return the minimum possible value of the maximum student load.

If there are more students than books, return -1.

Function

minimizeMaximumPages(pages: int[], students: int) → long

Examples

Example 1

pages = [12,34,67,90]students = 2return = 113

Allocate books [12,34,67] to the first student and [90] to the second. Their loads are 113 and 90, so the maximum load is 113. No valid allocation has a smaller maximum.

Example 2

pages = [10,20,30,40]students = 2return = 60

The allocation [10,20,30] and [40] has loads 60 and 40. Every other split produces a maximum load of at least 60.

Example 3

pages = [5,10,15]students = 4return = -1

There are more students than books, so it is impossible to give every student a non-empty segment.

Constraints

  • 1 <= pages.length <= 10^5
  • 1 <= pages[i] <= 10^9
  • 1 <= students <= 10^5

More Google problems

drafts saved locally
public long minimizeMaximumPages(int[] pages, int students) {
    // write your code here
}
pages[12,34,67,90]
students2
expected113
checking account