FastPrepFill a Time Window with Songs
Problems/Fill a Time Window with Songs

Fill a Time Window with Songs

Microsoft logoMicrosoft● MediumINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The round is one of a Microsoft software engineering internship process that the review does not name. Listing it as an online assessment is our guess. The task as reported is to fill a given stretch of time as fully as possible by picking songs, each of which occupies an interval. The author recalls it loosely, used sorting and binary search, and guessed it was greedy.

The exact rules are not given. Here every song is a fixed interval [start, end] that must lie fully inside the window [windowStart, windowEnd]. Chosen songs may touch but not overlap, and you return the largest total time filled. There are 1 to 10^4 songs and all times are from 0 to 10^9. In this version no simple greedy rule is always right, and the solution needs dynamic programming. Other readings fit the report too. One is picking the two songs with the largest total length that still fits the window, which also suits sorting plus binary search. Another is treating songs as plain lengths, which is a subset-sum task.

Our version is about 50% the same as the reported question.

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 <= starti and endi <= 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) → int

Examples

Example 1

songs = [[1,4],[3,9],[8,10]]windowStart = 0windowEnd = 10return = 6

Songs [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 = 8

Song [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 = 6

Song [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^4
  • songs[i].length == 2
  • 0 <= starti < endi <= 10^9
  • 0 <= 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

Interview reports that mention this question

  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)

Microsoft interview experiences

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public int maxFilledTime(int[][] songs, int windowStart, int windowEnd) {
        // Write your code here.
    }
}
Checking account…