Interval Usage with Non-Overlapping Overrides
Updated
Problem statement
You are given a timeline of days 1 to days. On each day a resource is either in use (1) or not in use (0). Two lists describe the timeline.
Every row of usage and every row of overrides is [l, r, v]. It describes the interval from day l to day r, with both days included, and a value v that is 0 or 1.
By default, a day is in use if at least one usage interval with value 1 covers it. A usage interval with value 0 adds nothing. It does not clear another usage interval.
An override interval forces every day it covers to its value v. Override intervals never overlap each other. On the days an override covers, the override wins over usage.
Return a string of length days made of the characters '0' and '1'. The character at position i, counting from 1, is the final state of day i.
For example, take days = 10, usage = [[1, 2, 1], [4, 10, 1]] and overrides = [[2, 4, 0]]. Usage puts days 1, 2 and 4 to 10 in use. The override sets days 2, 3 and 4 to 0. The final states are "1000111111".
Try to do better than simulating day by day. For example, O((U + O) log (U + O) + days) is possible, where U and O are the numbers of usage and override rows.
Function
dayStates(days: int, usage: int[][], overrides: int[][]) → StringExamples
Example 1
days = 10usage = [[1, 2, 1], [4, 10, 1]]overrides = [[2, 4, 0]]return = "1000111111"The usage intervals with value 1 cover days 1 to 2 and days 4 to 10. So before overrides, the states are 1, 1, 0, 1, 1, 1, 1, 1, 1, 1. The override [2, 4, 0] sets days 2, 3 and 4 to 0. The final states are 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, so the answer is "1000111111".
Constraints
1 <= days- Each row of
usageandoverridesis[l, r, v], wherevis 0 or 1. The intervals include both dayland dayr. - Usage is the union of all covering value
1usage intervals. - Override intervals do not overlap and take precedence over usage.
Similar questions at other companies
- Meeting Scheduling SystemHevo Data · ONSITE INTERVIEW
- Peak Task Concurrency IntervalsGoogle · ONSITE INTERVIEWGoogle interview questions
- Detect a Server RAM Capacity BreachMyntra · ONSITE INTERVIEWMyntra interview questions
- Peak Chat Load Across AgentsCresta · PHONE SCREENCresta interview questions
- Earliest Time to Schedule a MeetingMathWorks · OAMathWorks interview questions
- Earliest Meeting Start on a 24-Hour ClockIMC Trading · OAIMC Trading interview questions
- Majority Labels over Audio IntervalsNooks · PHONE SCREEN
- Earliest Time to Schedule a MeetingMicrosoft · OAMicrosoft interview questions
- Earliest Common Meeting StartVisa · OAVisa interview questions
- Smallest Most-Lit Street PositionHudson River Trading · OAHudson River Trading interview questions