Divide a Playlist Into K Segments to Minimize the Longest Segment's Total Duration
Solve this Problemdurations[i] seconds each — must be split into k contiguous segments (never splitting a single track, and every segment must hold at least one). Find the split that minimizes the longest single segment's total duration, and return that minimized maximum.
No segment limit below the single longest track could ever work (that track wouldn't fit under it at all), and a limit equal to the playlist's whole total duration always needs just one segment — so the answer is guaranteed to fall somewhere between those two bounds.
The number of segments needed only ever decreases (or stays flat) as the limit grows, which makes this a binary search on the answerBinary Search on the AnswerInstead of searching a sorted array, the search runs directly over the space of possible answers (here, every candidate segment limit). It works whenever "is this candidate good enough?" is monotonic — once a candidate works, every larger candidate keeps working too. — search directly over candidate segment limits rather than trying every possible way to split the playlist.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of tracks ≤ 1000 - ◆
0 ≤ durations[i] ≤ 10⁶ (seconds) - ◆
1 ≤ k ≤ number of tracks
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Segment Limit From the Longest Track Upward
BruteTracks must stay in playlist order, never split across segments — a segment keeps absorbing the next track until doing so would push it over some limit, at which point a new segment starts. No limit below the single longest track could ever work, and a limit equal to the whole playlist's total duration always fits in one segment — so the answer lies between those two bounds. Try every limit in that range, in order, counting how many segments it needs; the first limit that fits within k segments is the answer, since a bigger limit can only ever need the same number of segments or fewer. Correct, but scanning the whole playlist for every single candidate limit wastes a lot of work.
O(n · (sum − max))O(1)1class Solution {
2 public int minLargestSum(int[] durations, int k) {
3 int maxD = 0, sum = 0;
4 for (int d : durations) { maxD = Math.max(maxD, d); sum += d; }
5 for (int cap = maxD; cap <= sum; cap++) {
6 if (segmentsNeeded(durations, cap) <= k) return cap;
7 }
8 return sum;
9 }
10
11 private int segmentsNeeded(int[] durations, int cap) {
12 int segs = 1, total = 0;
13 for (int d : durations) {
14 if (total + d > cap) { segs++; total = 0; }
15 total += d;
16 }
17 return segs;
18 }
19}Optimal — Binary Search on the Segment Limit
OptimalThe number of segments needed only ever goes down (or stays the same) as the segment limit grows — a bigger limit can never need more segments. That monotonic relationship is exactly what binary search needs: search the candidate limits between the longest single track and the whole playlist's total duration, and whenever a candidate limit fits within k segments, remember it and try a smaller limit; otherwise it's too tight, so search bigger.
O(n · log(sum − max))O(1)1class Solution {
2 public int minLargestSum(int[] durations, int k) {
3 int lo = 0, hi = 0;
4 for (int d : durations) { lo = Math.max(lo, d); hi += d; }
5 int ans = hi;
6 while (lo <= hi) {
7 int mid = lo + (hi - lo) / 2;
8 if (segmentsNeeded(durations, mid) <= k) {
9 ans = mid;
10 hi = mid - 1;
11 } else {
12 lo = mid + 1;
13 }
14 }
15 return ans;
16 }
17
18 private int segmentsNeeded(int[] durations, int cap) {
19 int segs = 1, total = 0;
20 for (int d : durations) {
21 if (total + d > cap) { segs++; total = 0; }
22 total += d;
23 }
24 return segs;
25 }
26}