Fill a Time Window with Songs
Updated
Problem statement
You are given a list of songs, where songs[i] = [starti, endi] means song i can only be played from time starti to time endi, so it fills endi - starti minutes. You are also given a time window from windowStart to windowEnd.
Choose some of the songs (possibly none) so that:
- every chosen song lies completely inside the window (
windowStart <= startiandendi <= windowEnd), and - no two chosen songs overlap in time. A song may start exactly when another one ends.
Return the largest total number of minutes the chosen songs can fill.
Function
maxFilledTime(songs: int[][], windowStart: int, windowEnd: int) → intExamples
Example 1
songs = [[1,4],[3,9],[8,10]]windowStart = 0windowEnd = 10return = 6Songs [1, 4] and [8, 10] do not overlap and fill 3 + 2 = 5 minutes. Song [3, 9] overlaps both of them, but on its own it fills 6 minutes, which is more. The answer is 6.
Example 2
songs = [[0,5],[5,8],[2,6]]windowStart = 0windowEnd = 8return = 8Song [0, 5] ends exactly when [5, 8] starts, so both can be played. Together they fill the whole window: 5 + 3 = 8.
Example 3
songs = [[0,6],[0,3],[3,6],[5,12]]windowStart = 0windowEnd = 10return = 6Song [5, 12] ends after the window ends at 10, so it cannot be used. The best is [0, 6] alone, or [0, 3] with [3, 6], and both fill 6 minutes.
Constraints
1 <= songs.length <= 10^4songs[i].length == 20 <= starti < endi <= 10^90 <= windowStart < windowEnd <= 10^9
More Microsoft Online Assessment questions
- Minimum Cost to Process Priority TasksOA · Seen Nov 2026
- Most Visited Sprint MarkerOA · Seen Nov 2026
- Maximum Escape Game ScoreOA · Seen Nov 2026
- Count Subarrays with a Perfect-Square ProductOA · Seen Nov 2026
- Maximum Interactive Team SizeOA · Seen Nov 2026
- Maximize Pipeline Throughput Under a Scaling BudgetOA · Seen Nov 2026
- Minimum Cost K-Capable ModelsOA · Seen Nov 2026
- Find Available Meeting RoomsOA · Seen Oct 2026
- Maximum Sum of a K-StarOA · Seen Oct 2026
- Capacity to Ship Packages Within DaysOA · ONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Maximum Taxi EarningsWells Fargo · OAWells Fargo interview questions
- Maximum Total Length of Non-Overlapping IntervalsBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Russian Doll EnvelopesGoogle · ONSITE INTERVIEWGoogle interview questions
- Maximum Profit in Job SchedulingAmazon · PHONE SCREEN
- Russian Doll EnvelopesInMobi · ONSITE INTERVIEWInMobi interview questions
- Longest Increasing Price SubsequenceOpenAI · OAOpenAI interview questions
- Linear InterpolatorTwo Sigma · OATwo Sigma interview questions
- Choose ContainersIMC Trading · OAIMC Trading interview questions
- Minimum Cost to Attend Required CoursesVisa · OAVisa interview questions
- Minimize Maximum Group DifferenceDRW · OADRW interview questions