Why Intervals Are a Common Problem Pattern in DSA Typescript - Why This Pattern

Mental Model

Intervals represent ranges of values that often overlap or need merging, making them a common pattern in problems involving scheduling or grouping.

Analogy: Imagine booking meeting rooms where each meeting has a start and end time; you need to see which meetings overlap or fit together without conflict.

Time line:
|----|----|----|----|----|----|----|----|
Meetings:
[1---3]  [2----5]    [6---8]
Overlap:
[1---5]          [6---8]

Dry Run Walkthrough

Input: Intervals: [1,3], [2,5], [6,8]

Goal: Show how overlapping intervals merge into one combined interval

Step 1: Sort intervals by start time

[1,3] -> [2,5] -> [6,8]

Why: Sorting helps to process intervals in order and detect overlaps easily

Step 2: Start with first interval [1,3] as current merged interval

Merged: [1,3]

Why: We need a base interval to compare others against

Step 3: Compare next interval [2,5] with merged [1,3]; they overlap

Merged updated to [1,5]

Why: Overlapping intervals combine into one bigger interval

Step 4: Compare next interval [6,8] with merged [1,5]; no overlap

Merged intervals: [1,5], [6,8]

Why: Non-overlapping intervals stay separate

Result:

[1,5] -> [6,8]

Annotated Code

DSA Typescript

class Interval {
  constructor(public start: number, public end: number) {}
}

function mergeIntervals(intervals: Interval[]): Interval[] {
  if (intervals.length === 0) return [];

  intervals.sort((a, b) => a.start - b.start); // sort intervals by start

  const merged: Interval[] = [];
  let current = intervals[0];

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i].start <= current.end) {
      // overlap detected, merge intervals
      current.end = Math.max(current.end, intervals[i].end);
    } else {
      // no overlap, push current and update
      merged.push(current);
      current = intervals[i];
    }
  }
  merged.push(current); // push last interval
  return merged;
}

// Driver code
const intervals = [new Interval(1, 3), new Interval(2, 5), new Interval(6, 8)];
const merged = mergeIntervals(intervals);
for (const interval of merged) {
  console.log(`[${interval.start},${interval.end}]`);
}

intervals.sort((a, b) => a.start - b.start); // sort intervals by start

sort intervals to process in order

let current = intervals[0];

initialize current merged interval

if (intervals[i].start <= current.end) {

check if intervals overlap

current.end = Math.max(current.end, intervals[i].end);

merge overlapping intervals by extending end

merged.push(current);

add non-overlapping interval to result

current = intervals[i];

update current to new interval

merged.push(current);

add last interval after loop

Output

[1,5]

[6,8]

Complexity Analysis

Time: O(n log n) because sorting the intervals dominates the time

Space: O(n) because in worst case no intervals overlap and all are stored

vs Alternative: Naive approach checks every pair for overlap O(n^2), this method is faster due to sorting and single pass merge

Edge Cases

empty intervals list

returns empty list immediately

DSA Typescript

if (intervals.length === 0) return [];

all intervals non-overlapping

returns all intervals as is

DSA Typescript

else branch where intervals[i].start > current.end

all intervals overlapping

returns one merged interval covering all

DSA Typescript

current.end = Math.max(current.end, intervals[i].end);

When to Use This Pattern

When you see problems about ranges, times, or segments that may overlap or need grouping, think of the intervals pattern because sorting and merging simplifies the problem.

Common Mistakes

Mistake: Not sorting intervals before merging
Fix: Always sort intervals by start time first to ensure correct merging order

Mistake: Not updating the current merged interval's end correctly
Fix: Use max of current end and new interval end to extend merged interval properly

Summary

It merges overlapping intervals into combined ranges.

Use it when handling problems with overlapping time or value ranges.

Sorting intervals by start time lets you merge in one pass efficiently.

Practice

1. Why are interval problems common in data structures and algorithms?

easy

A. Because they help solve scheduling and merging tasks efficiently

B. Because they only involve sorting numbers

C. Because they require complex graph traversal

D. Because they always use recursion

Solution

1. Step 1: Understand the nature of interval problems

   Interval problems often involve ranges of values, like time slots or numeric ranges, which are common in real-world tasks such as scheduling.

2. Step 2: Identify why intervals are useful

   Intervals allow efficient merging and checking overlaps, which are key in many applications like calendar events or resource allocation.

3. Final Answer:

   Because they help solve scheduling and merging tasks efficiently -> Option A

4. Quick Check:

   Intervals = scheduling and merging [OK]

Hint: Think about real-life tasks like booking or meetings [OK]

Common Mistakes:

• Assuming intervals only involve sorting
• Confusing intervals with graph problems
• Thinking recursion is always needed

2. Which TypeScript syntax correctly declares an interval as a tuple of two numbers?

easy

A. let interval: tuple = [5, 10];

B. let interval = (5, 10);

C. let interval: number[] = (5, 10);

D. let interval: [number, number] = [5, 10];

Solution

1. Step 1: Recall TypeScript tuple syntax

   Tuples in TypeScript are declared with square brackets and types inside, like [number, number].

2. Step 2: Check each option

   let interval: [number, number] = [5, 10]; correctly uses tuple syntax. let interval = (5, 10); uses parentheses which is invalid. let interval: number[] = (5, 10); uses array type but assigns parentheses. let interval: tuple = [5, 10]; uses 'tuple' which is not a TypeScript type.

3. Final Answer:

   let interval: [number, number] = [5, 10]; -> Option D

4. Quick Check:

   Tuple syntax = [number, number] [OK]

Hint: Tuples use square brackets with types inside [OK]

Common Mistakes:

• Using parentheses instead of square brackets
• Using 'tuple' as a type keyword
• Confusing arrays with tuples

3. What is the output of this TypeScript code that merges overlapping intervals?

function mergeIntervals(intervals: [number, number][]): [number, number][] {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged: [number, number][] = [];
  for (const interval of intervals) {
    if (!merged.length || merged[merged.length - 1][1] < interval[0]) {
      merged.push(interval);
    } else {
      merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
    }
  }
  return merged;
}

console.log(mergeIntervals([[1,3],[2,6],[8,10],[15,18]]));

medium

A. [[1,6],[8,10],[15,18]]

B. [[1,3],[2,6],[8,10],[15,18]]

C. [[1,6],[2,6],[8,10],[15,18]]

D. [[1,3],[8,10],[15,18]]

Solution

1. Step 1: Sort intervals by start time

   The intervals become [[1,3],[2,6],[8,10],[15,18]].

2. Step 2: Merge overlapping intervals

   First interval [1,3] is added. Next [2,6] overlaps with [1,3], so merge to [1,6]. Then [8,10] and [15,18] do not overlap, so added as is.

3. Final Answer:

   [[1,6],[8,10],[15,18]] -> Option A

4. Quick Check:

   Merged intervals = [[1,6],[8,10],[15,18]] [OK]

Hint: Sort intervals first, then merge overlapping ones [OK]

Common Mistakes:

• Not sorting intervals before merging
• Overwriting intervals incorrectly
• Missing to merge overlapping intervals

4. Find the error in this TypeScript function that checks if two intervals overlap:

function isOverlap(a: [number, number], b: [number, number]): boolean {
  return a[1] > b[0] && b[1] > a[0];
}

medium

A. The function should return a number, not boolean

B. The intervals should be arrays of strings, not numbers

C. The comparison should use >= instead of > to include touching intervals

D. The function is correct as is

Solution

1. Step 1: Understand interval overlap condition

   Two intervals overlap if they share any point, including touching at edges.

2. Step 2: Check the comparison operators

   Using > excludes intervals that just touch (like [1,2] and [2,3]). Using >= includes touching intervals as overlapping.

3. Final Answer:

   The comparison should use >= instead of > to include touching intervals -> Option C

4. Quick Check:

   Use >= for touching intervals overlap [OK]

Hint: Use >= to count touching intervals as overlapping [OK]

Common Mistakes:

• Using > excludes touching intervals
• Returning wrong data type
• Wrong interval data types

5. Given a list of intervals representing booked meeting times, how would you find the minimum number of meeting rooms required?
Choose the best approach.

hard

A. Count intervals and divide by two

B. Sort intervals by start time, use a min-heap to track end times, count rooms needed

C. Use recursion to check all combinations of intervals

D. Sort intervals by end time, merge all intervals into one

Solution

1. Step 1: Understand the problem of meeting rooms

   We need to find how many meetings overlap at the same time to know rooms needed.

2. Step 2: Use sorting and a min-heap

   Sort intervals by start time. Use a min-heap to track earliest ending meeting. If a meeting starts after the earliest ends, reuse room; else add a new room.

3. Step 3: Count the maximum size of the heap

   The heap size at any time is the number of rooms needed.

4. Final Answer:

   Sort intervals by start time, use a min-heap to track end times, count rooms needed -> Option B

5. Quick Check:

   Min rooms = max overlapping intervals [OK]

Hint: Track earliest end times with min-heap to count rooms [OK]

Common Mistakes:

• Merging intervals loses overlap info
• Using recursion causes inefficiency
• Simple division ignores overlaps