Sort + Merge Overlapping Ranges
Click "Start" or "Step" to begin the algorithm
Medium
Find minimum removals to make intervals non-overlapping.
Solve on LeetCode →Medium
Find intersections of two interval lists.
Solve on LeetCode →The key insight: Sort by start time, then merge in one pass!
function merge(intervals) {
if (intervals.length === 0) return [];
// Step 1: Sort by start time
intervals.sort((a, b) => a[0] - b[0]);
const result = [intervals[0]];
// Step 2: Iterate and merge
for (let i = 1; i < intervals.length; i++) {
const current = intervals[i];
const last = result[result.length - 1];
// Check overlap: current starts before last ends
if (current[0] <= last[1]) {
// Merge: extend the end time
last[1] = Math.max(last[1], current[1]);
} else {
// No overlap: add as new interval
result.push(current);
}
}
return result;
}Use a min-heap to track room end times efficiently!
function minMeetingRooms(intervals) {
if (intervals.length === 0) return 0;
// Sort by start time
intervals.sort((a, b) => a[0] - b[0]);
// Min-heap for end times
const rooms = [intervals[0][1]];
for (let i = 1; i < intervals.length; i++) {
// If earliest ending meeting ends before this starts
if (rooms[0] <= intervals[i][0]) {
rooms.shift(); // Room freed
}
// Add current meeting's end time
rooms.push(intervals[i][1]);
rooms.sort((a, b) => a - b); // Keep as min-heap
}
return rooms.length; // Peak number of rooms
}