491. Painter's Partition Problem

MediumBinary SearchBinary Search on AnswerArray

Given board lengths arranged in order and a number of painters, each painter paints contiguous boards and all painters work simultaneously at the same speed. Return the minimum time to paint all boards, where time equals the maximum total length any single painter paints. Input: '[boards], painters'.

Input: '[boards], painters'.

Output: Integer — the minimum painting time.

Examples

Example 1
Input: [10,20,30,40], 2
Output: 60
Explanation: [10,20,30] and [40].
Example 2
Input: [5,10,30,20,15], 3
Output: 35
Explanation: Best partition gives max 35.
Example 3
Input: [100], 1
Output: 100
Explanation: Single board.

Constraints

Asked by

AmazonMicrosoftGoogleAdobeFlipkart
Solve this problem in the editor →