Most Disjoint Intervals From Starts and Durations
Updated
Problem statement
You are given two integer arrays of the same length, start and duration. Interval i begins at time start[i] and lasts duration[i], so it runs from start[i] up to, but not including, start[i] + duration[i].
A group of intervals is clash-free when no moment of time is covered by two of them. The end time is not part of an interval, so [1, 3) and [3, 7) form a clash-free group, but [1, 4) and [3, 7) do not: the time from 3 to 4 is covered by both.
Return the size of the largest clash-free group you can form from the given intervals.
The intervals may come in any order, and the same interval can be listed more than once.
Function
maxDisjointIntervals(start: int[], duration: int[]) → intExamples
Example 1
start = [1,3,0,5,8,5]duration = [3,2,6,2,1,4]return = 3The intervals are [1, 4), [3, 5), [0, 6), [5, 7), [8, 9) and [5, 9). Pick [1, 4), [5, 7) and [8, 9): none of them share any time. You cannot pick 4. [1, 4), [3, 5) and [0, 6) all cover the moment 3.5, so at most one of them fits. [5, 7) and [5, 9) both cover the moment 5, so at most one of those fits. Only [8, 9) is left, so the answer is 3.
Example 2
start = [2,4,6]duration = [2,2,2]return = 3The intervals are [2, 4), [4, 6) and [6, 8). Each one ends exactly when the next starts. Touching is allowed, so all 3 can be picked.
Example 3
start = [10,10,11]duration = [5,5,1]return = 1The intervals are [10, 15), [10, 15) and [11, 12). All three share the time from 11 to 12, so only 1 can be picked.
Constraints
1 <= start.length <= 10^4duration.length == start.length0 <= start[i] <= 10^91 <= duration[i] <= 10^9
More DocuSign Online Assessment questions
- Max Sum With No Two Adjacent PicksOA · Seen Apr 2026
- Max Sum With No Two Adjacent Picks on a CircleOA · Seen Apr 2026
- Beautiful Number OrderingsOA · Seen Feb 2026
- Grid Path With the Most ClearanceOA · Seen May 2025
- Vehicle Mixes for a Wheel TotalOA · Seen May 2025
- Count Sales Rung Up at the Wrong PriceOA · Seen Feb 2021
- Fewest Fountains to Water the GardenOA · Seen Feb 2021
- Lowest Start That Keeps Running Totals PositiveOA · Seen Feb 2021
- Fewest Student Groups Within a Level GapOA · Seen Nov 2020
- Alphabetize a Word ListOA · Seen May 2020
Similar questions at other companies
- Maximum Compatible Time WindowsIBM · OAIBM interview questions
- Minimum Markers to Clear Line SegmentsHSBC · OAHSBC interview questions
- Minimum Machines for TasksExpedia · OAExpedia interview questions
- University Career FairRoblox · OARoblox interview questions
- Minimum Removals for Non-Overlapping IntervalsByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions
- Maximum Number of Events That Can Be AttendedSnowflake · PHONE SCREENSnowflake interview questions
- Minimum Workers with Job AssignmentsLyft · ONSITE INTERVIEWLyft interview questions
- Minimum Appointment Cancellations with a Required BreakMaven Clinic · PHONE SCREENMaven Clinic interview questions
- Minimum Removals for Non-Overlapping IntervalsBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Minimum Meeting RoomsSentry · PHONE SCREENSentry interview questions