If we know the interval numbers are limited to 24 hours in a day (or some other constant time interval) we can implement bucket sort or count sort instead of a general purpose sort, both of which run at O(n).
For example: (This is a combination of bucket and count sort). We create 24 buckets and within each bucket we store the length of each interval (effectively using the length of intervals as the second sorting factor). Then, we count the number of intervals that have the same start point and length, and lastly, recreate the list of intervals. space is O(n) and time is also O(n).
const intervalSort = (intervals) => {
const buckets = new Array(23);
for (const interval of intervals) {
buckets[interval.start] = buckets[interval.start] || new Array(23 - interval.start);
buckets[interval.start][interval.end - interval.start] = (buckets[interval.start][interval.end - interval.start] || 0) + 1;
}
const result = [];
for (let i = 0; i < 24; i++) {
const lengths = buckets[i];
if (lengths) {
for (let j = 0; j < lengths.length; j++) {
const count = lengths[j]
if (typeof count !== 'undefined') {
for (let k = 0; k < count; k++) {
result.push(new Interval(i, i + j));
}
}
}
}
}
return result;
}