A interval is usually represented as pairs, representing a range, often in time or space:
[1, 3] could mean a meeting from 1 to 3[2, 4] could mean memory allocated from address 2 to 4type Interval struct {
Start int
End int
}
By Sorting-by-start, discovering overlapping intervals is only compare intervalA.End with intervalB.Start.
sort.Slice(intervals, func(i, j int) bool {
return intervals[i].Start < intervals[j].Start
})
If you're trying to greedily pick the earliest finishing intervals
| Problem Type | Time Complexity | Space Complexity |
|---|---|---|
| Merge Intervals | O(n log n) (sort) |
O(n) |
| Insert Interval | O(n) |
O(n) |
| Max Non-overlapping Intervals | O(n log n) (sort) |
O(1) |
| Interval Intersections | O(n + m) |
O(min(n, m)) |
https://leetcode.com/problems/meeting-rooms/description/?envType=problem-list-v2&envId=v2f76tps