MediumIntervals
Non-overlapping Intervals
Remove minimum intervals for non-overlap
Solution Approach
Sort intervals by start time. Merge overlapping intervals by comparing end of current with start of next. Use stack or array to track merged intervals.
Implementation
def merge(intervals):
intervals.sort()
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1] = (merged[-1][0], max(merged[-1][1], end))
else:
merged.append((start, end))
return mergedComplexity Analysis
Time Complexity
O(n log n)Space Complexity
O(1)Key Learning Points
Sort by start timeCompare overlapsTrack merged result
Related Problems to Practice
Merge IntervalsInsert IntervalMeeting Rooms
Complexity
Time:O(n log n)
Space:O(1)
Asked at
GoogleFacebook