The task is to merge a list of intervals. Overlapping intervals must be merged, separate kept separate. See complete documentation online or local as PDF.
Following things were not described and are expected:
- Providing an empty list, returns an empty list.
- NULL as input raises an IllegalArgumentException.
The input interval list is sorted by the intervals start. Having this simply the intervals can be processed one after the other and checking for gaps when taking the next interval.
The time complexity of the interval merge is because of the sorting O(n*log(n)). The sorting is more complex than the merging of the intervals having the time complexity O(n).
Being x the memory consumption of one interval, n the size of the input interval and m the size of the result interval: The overall memory consumption is ( n + m ) * x.
As standard java.util classes are used the execution scales ideally.
./gradlew build
./gradlew run
- 2020-11-24 19:15 - 21:35