MediumGreedy
Interval Scheduling
Maximum non-overlapping intervals
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
GoogleAmazon