Managing Intervals and Ranges
1. Implementing Interval Trees
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Insert | Insert an interval into the tree | O(log n) | O(n) |
| Delete | Remove an interval from the tree | O(log n) | O(n) |
| Search | Find intervals overlapping with a given interval | O(log n + k) | O(n) |
Example: Basic Interval Tree Node
class IntervalNode {
constructor(interval, max) {
this.interval = interval;
this.max = max;
this.left = null;
this.right = null;
}
}
const interval1 = { start: 15, end: 20 };
const node = new IntervalNode(interval1, 20);
Example: Insert Interval
function insert(root, interval) {
if (root === null) {
return new IntervalNode(interval, interval.end);
}
if (interval.start < root.interval.start) {
root.left = insert(root.left, interval);
} else {
root.right = insert(root.right, interval);
}
if (root.max < interval.end) {
root.max = interval.end;
}
return root;
}
Example: Search Overlapping Intervals
function search(root, interval) {
const result = [];
if (root === null) return result;
if (doOverlap(root.interval, interval)) {
result.push(root.interval);
}
if (root.left !== null && root.left.max >= interval.start) {
result.push(...search(root.left, interval));
}
return search(root.right, interval);
}
function doOverlap(interval1, interval2) {
return interval1.start <= interval2.end && interval2.start <= interval1.end;
}
Note: The interval tree is a binary search tree where each node stores an interval and the maximum endpoint of all intervals in its subtree.
2. Finding Overlapping Intervals
| Property | Description | Example |
|---|---|---|
| intervals | List of intervals represented as [start, end] | [[1, 3], [2, 6], [8, 10]] |
| overlap | Boolean indicating if intervals overlap | true |
Example: Check for Overlapping Intervals
function hasOverlappingIntervals(intervals) {
for (let i = 0; i < intervals.length - 1; i++) {
const [start1, end1] = intervals[i];
const [start2, end2] = intervals[i + 1];
if (end1 >= start2) {
return true;
}
}
return false;
}
const intervals = [[1, 3], [2, 6], [8, 10]];
console.log(hasOverlappingIntervals(intervals)); // trueExample: Merge Overlapping Intervals
function mergeOverlappingIntervals(intervals) {
if (intervals.length <= 1) return intervals;
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const [start, end] = intervals[i];
const lastEnd = merged[merged.length - 1][1];
if (start <= lastEnd) {
merged[merged.length - 1][1] = Math.max(lastEnd, end);
} else {
merged.push(intervals[i]);
}
}
return merged;
}
const intervals = [[1, 3], [2, 6], [8, 10], [15, 18]];
console.log(mergeOverlappingIntervals(intervals)); // [[1, 6], [8, 10], [15, 18]]
Note: Merging overlapping intervals is a common pattern in interval scheduling and resource allocation problems.
3. Implementing Range Module
| Method | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| addRange(left, right) | Adds the half-open interval [left, right) to the set of ranges | O(n) | O(n) |
| queryRange(left, right) | Checks if every number in [left, right) is being tracked | O(n) | O(1) |
| removeRange(left, right) | Removes the half-open interval [left, right) from the set of ranges | O(n) | O(n) |
Example: Basic Range Module Implementation
class RangeModule {
constructor() {
this.ranges = [];
}
addRange(left, right) {
const newRanges = [];
let i = 0;
while (i < this.ranges.length && this.ranges[i][1] < left) {
newRanges.push(this.ranges[i]);
i++;
}
while (i < this.ranges.length && this.ranges[i][0] <= right) {
left = Math.min(left, this.ranges[i][0]);
right = Math.max(right, this.ranges[i][1]);
i++;
}
newRanges.push([left, right]);
while (i < this.ranges.length) {
newRanges.push(this.ranges[i]);
i++;
}
this.ranges = newRanges;
}
queryRange(left, right) {
for (const [start, end] of this.ranges) {
if (start <= left && right <= end) {
return true;
}
}
return false;
}
removeRange(left, right) {
const newRanges = [];
let i = 0;
while (i < this.ranges.length && this.ranges[i][1] < left) {
newRanges.push(this.ranges[i]);
i++;
}
while (i < this.ranges.length && this.ranges[i][0] < right) {
const start = Math.max(left, this.ranges[i][0]);
const end = Math.min(right, this.ranges[i][1]);
if (start > this.ranges[i][0]) {
newRanges.push([this.ranges[i][0], start]);
}
if (end < this.ranges[i][1]) {
newRanges.push([end, this.ranges[i][1]]);
}
i++;
}
while (i < this.ranges.length) {
newRanges.push(this.ranges[i]);
i++;
}
this.ranges = newRanges;
}
}
const rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
console.log(rangeModule.queryRange(14, 16)); // true
rangeModule.removeRange(15, 18);
console.log(rangeModule.queryRange(14, 16)); // false4. Implementing My Calendar
| Method | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| MyCalendar() | Initializes an empty calendar | O(1) | O(1) |
| book(start, end) | Books a new interval [start, end) if it doesn't overlap | O(n) | O(n) |
Example: My Calendar Implementation
class MyCalendar {
constructor() {
this.events = [];
}
book(start, end) {
for (let [s, e] of this.events) {
if (start < e && end > s) {
return false;
}
}
this.events.push([start, end]);
return true;
}
}
const calendar = new MyCalendar();
console.log(calendar.book(10, 20)); // true
console.log(calendar.book(15, 25)); // false
Note: The interval is booked only if it does not overlap with any existing event. Events are stored as [start, end) intervals.
5. Solving Meeting Rooms III
Meeting Rooms III is a variant of the classic meeting room scheduling problem where you are given a list of meetings with start and end times, and you need to determine the room that hosts the most meetings.
This problem can be solved using a min-heap to keep track of room availability times and a counter to track how many meetings each room hosts.
| Property | Description | Example |
|---|---|---|
| meetings | List of meetings with start and end times | [[0, 10], [10, 20], [20, 30]] |
| rooms | Number of rooms available | 2 |
Example: Meeting Rooms III
function maxMeetings(meetings, rooms) {
const roomCount = new Array(rooms).fill(0);
const minHeap = new MinHeap();
meetings.sort((a, b) => a[0] - b[0]);
for (const [start, end] of meetings) {
const earliest = minHeap.peek();
if (earliest && earliest <= start) {
minHeap.pop();
const roomIndex = roomCount.indexOf(earliest);
roomCount[roomIndex]++;
minHeap.push(end);
} else {
const freeRoom = roomCount.indexOf(0);
if (freeRoom !== -1) {
roomCount[freeRoom]++;
minHeap.push(end);
}
}
}
return roomCount.indexOf(Math.max(...roomCount));
}
class MinHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this.bubbleUp(this.heap.length - 1);
}
pop() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown(0);
return min;
}
peek() {
return this.heap[0];
}
bubbleUp(index) {
if (index === 0) return;
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[parentIndex] > this.heap[index]) {
[this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
this.bubbleUp(parentIndex);
}
}
bubbleDown(index) {
const leftChild = 2 * index + 1;
const rightChild = 2 * index + 2;
let minIndex = index;
if (leftChild < this.heap.length && this.heap[leftChild] < this.heap[minIndex]) {
minIndex = leftChild;
}
if (rightChild < this.heap.length && this.heap[rightChild] < this.heap[minIndex]) {
minIndex = rightChild;
}
if (minIndex !== index) {
[this.heap[index], this.heap[minIndex]] = [this.heap[minIndex], this.heap[index]];
this.bubbleDown(minIndex);
}
}
}
Note: The solution uses a min-heap to efficiently manage room availability and track the number of meetings per room.
6. Finding Data Stream Disjoint Intervals
When processing a stream of intervals, the goal is to maintain a set of disjoint (non-overlapping) intervals that cover all the data received so far. This is useful in scenarios like merging live updates to a timeline or tracking resource usage over time.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Insert Interval | Adds a new interval to the existing set of disjoint intervals. | O(n) | O(1) extra |
| Merge Overlapping | Merges overlapping intervals into disjoint ones. | O(n log n) | O(1) extra |
| Query Range | Checks if a given interval overlaps with any existing intervals. | O(log n) | O(1) |
Example: Insert Interval
function insertInterval(intervals, newInterval) {
const result = [];
let i = 0;
const n = intervals.length;
// Add all intervals before newInterval that do not overlap
while (i < n && intervals[i][1] < newInterval[0]) {
result.push(intervals[i]);
i++;
}
// Merge overlapping intervals
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.push(newInterval);
// Add remaining intervals
while (i < n) {
result.push(intervals[i]);
i++;
}
return result;
}
// Example usage:
const intervals = [[1,3],[6,9]];
const newInterval = [2,5];
console.log(insertInterval(intervals, newInterval)); // [[1,5],[6,9]]
Example: Merge Overlapping Intervals
function mergeIntervals(intervals) {
if (intervals.length <= 1) return intervals;
// Sort intervals by start time
intervals.sort((a, b) => a[0] - b[0]);
const result = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = result[result.length - 1];
const current = intervals[i];
if (last[1] >= current[0]) {
// Overlap, merge
last[1] = Math.max(last[1], current[1]);
} else {
// No overlap, add new interval
result.push(current);
}
}
return result;
}
// Example usage:
const intervals2 = [[1,3],[2,6],[8,10],[15,18]];
console.log(mergeIntervals(intervals2)); // [[1,6],[8,10],[15,18]]
Note: For data streams, maintaining a sorted list or using an interval tree can improve performance for frequent insertions and queries.
7. Implementing Count of Range Sum
The "Count of Range Sum" problem involves counting the number of range sums within a given target range [lower, upper]. This is commonly solved using a modified merge sort algorithm to achieve O(n log n) time complexity.
| Property | Description | Notes |
|---|---|---|
| Input | An array of integers and a range [lower, upper] | Array can contain negative numbers |
| Output | Number of range sums in [lower, upper] | Range sum is sum of elements from index i to j |
| Time Complexity | O(n log n) | Using merge sort with prefix sums |
| Space Complexity | O(n) | For storing prefix sums and temporary arrays |
Example: Count of Range Sum
function countRangeSum(nums, lower, upper) {
const prefix = [0];
for (let i = 0; i < nums.length; i++) {
prefix.push(prefix[prefix.length - 1] + nums[i]);
}
function mergeSort(left, right) {
if (left >= right) return 0;
const mid = Math.floor((left + right) / 2);
let count = mergeSort(left, mid) + mergeSort(mid + 1, right);
// Count valid ranges
let j = mid + 1, k = mid + 1;
for (let i = left; i <= mid; i++) {
while (j <= right && prefix[j] - prefix[i] < lower) j++;
while (k <= right && prefix[k] - prefix[i] <= upper) k++;
count += k - j;
}
// Merge the two sorted halves
const temp = [];
let l = left, r = mid + 1;
while (l <= mid || r <= right) {
if (r > right || (l <= mid && prefix[l] <= prefix[r])) {
temp.push(prefix[l++]);
} else {
temp.push(prefix[r++]);
}
}
for (let i = 0; i < temp.length; i++) {
prefix[left + i] = temp[i];
}
return count;
}
return mergeSort(0, prefix.length - 1);
}
// Example usage:
const nums = [-2, 5, -1];
const lower = -2;
const upper = 2;
console.log(countRangeSum(nums, lower, upper)); // Output: 3
Note: The algorithm uses prefix sums to convert the problem into counting pairs (i, j) where
lower <= prefix[j] - prefix[i] <= upper. This is efficiently done using merge sort's divide-and-conquer approach.
8. Finding Skyline Problem
The Skyline problem involves determining the outline of buildings when viewed from a distance. Given a list of buildings with their positions and heights, the task is to return the key points that define the skyline.
| Property | Description | Notes |
|---|---|---|
| Building | Each building is defined by [left, right, height] | Left and right are x-coordinates; height is the building's height |
| Skyline Points | Points where the skyline changes height | Must be sorted by x-coordinate and represent local maxima |
Example: Skyline Calculation
function getSkyline(buildings) {
const events = [];
for (const [left, right, height] of buildings) {
events.push([left, -height, 'start']);
events.push([right, height, 'end']);
}
events.sort((a, b) => {
if (a[0] !== b[0]) return a[0] - b[0];
return a[1] - b[1];
});
const result = [];
const heights = [0];
let prevMax = 0;
for (const [x, h, type] of events) {
if (type === 'start') {
heights.push(-h);
} else {
const index = heights.indexOf(h);
heights.splice(index, 1);
}
const currentMax = Math.max(...heights);
if (currentMax !== prevMax) {
result.push([x, currentMax]);
prevMax = currentMax;
}
}
return result;
}
// Example usage:
const buildings = [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]];
console.log(getSkyline(buildings));
Note: The skyline points are defined by the x-coordinate and the maximum height at that point. The algorithm uses a sweep line approach with events to process building starts and ends.
Algorithm Summary
- Process each building as two events: start and end
- Sort events by x-coordinate, with special handling for same x-coordinates
- Maintain a list of active building heights
- At each event, update the height list and check for skyline changes
9. Solving Rectangle Area
| Property | Description | Example |
|---|---|---|
| area | Calculates the area of a rectangle given its width and height | width * height |
| perimeter | Calculates the perimeter of a rectangle | 2 * (width + height) |
| diagonal | Calculates the diagonal length of a rectangle using Pythagorean theorem | Math.sqrt(width^2 + height^2) |
Example: Calculating Rectangle Area
const width = 5;
const height = 3;
const area = width * height;
console.log(area); // Output: 15Example: Calculating Rectangle Perimeter
const width = 5;
const height = 3;
const perimeter = 2 * (width + height);
console.log(perimeter); // Output: 16Example: Calculating Rectangle Diagonal
const width = 5;
const height = 3;
const diagonal = Math.sqrt(width * width + height * height);
console.log(diagonal); // Output: ~5.83
Note: When working with rectangles, ensure that all dimensions are in the same units before performing calculations.
10. Finding Perfect Rectangle
| Property | Description | Notes |
|---|---|---|
| input | int[][] rectangles |
Array of rectangles, each defined by [x1, y1, x2, y2] |
| output | boolean |
True if rectangles form a perfect rectangle |
Example: Valid Perfect Rectangle
const rectangles = [
[1, 1, 3, 3],
[3, 1, 4, 2],
[3, 2, 4, 4],
[1, 3, 2, 4],
[2, 3, 3, 4]
];
// Expected: trueExample: Invalid Perfect Rectangle
const rectangles = [
[1, 1, 2, 3],
[1, 3, 2, 4],
[2, 1, 3, 2],
[2, 2, 3, 4]
];
// Expected: false
Note: A perfect rectangle is formed when rectangles completely fill a rectangular area with no gaps or overlaps.