Maximum Non-Overlapping Intervals
Updated
Problem statement
You are given a list of intervals, where intervals[i] = [start_i, end_i] is an activity that runs from time start_i to time end_i. Two intervals overlap if they share any time strictly inside both of them. An interval that ends exactly when another starts does not overlap it.
Return the largest number of intervals you can choose so that no two chosen intervals overlap. Intervals may repeat, and the list may be in any order.
Function
maxNonOverlapping(intervals: int[][]) → intExamples
Example 1
intervals = [[1,3],[2,4],[3,5],[6,8],[7,9]]return = 3Choose [1, 3], [3, 5] and [6, 8]; the first two only touch at 3, which is allowed. Four is impossible: [1, 3] and [2, 4] overlap, and so do [6, 8] and [7, 9], so at most one interval from each of those pairs can be chosen, plus [3, 5].
Example 2
intervals = [[1,2],[2,3],[3,4],[1,3]]return = 3[1, 2], [2, 3] and [3, 4] only touch at their ends, which does not count as overlapping, so all three can be chosen.
Constraints
1 <= intervals.length <= 10^4andintervals[i].length == 20 <= start_i < end_i <= 10^9
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Minimum Railway PlatformsMakeMyTrip.com · ONSITE INTERVIEWMakeMyTrip.com interview questions
- Minimum Removals for Non-Overlapping IntervalsByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions
- Minimum Workers with Job AssignmentsLyft · ONSITE INTERVIEWLyft interview questions
- Minimum Points Hitting Every Closed IntervalGoogle · ONSITE INTERVIEWGoogle interview questions
- Minimum Removals for Non-Overlapping IntervalsBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Maximum Compatible Time WindowsIBM · OAIBM interview questions
- Task SchedulingJP Morgan Chase · OAJP Morgan Chase interview questions
- Maximum Number of Events That Can Be AttendedSnowflake · PHONE SCREENSnowflake interview questions
- Minimum Appointment Cancellations with a Required BreakMaven Clinic · PHONE SCREENMaven Clinic interview questions
- Minimum Markers to Clear Line SegmentsHSBC · OAHSBC interview questions
Interview reports that mention this question
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)
- Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)