Why Intervals Are a Common Problem Pattern in DSA Typescript - Why It Works

Concept Flow - Why Intervals Are a Common Problem Pattern

Start with list of intervals

↓

Sort intervals by start time

↓

Initialize merged list with first interval

↓

For each next interval

↓

Check if current interval overlaps with last merged

↓

Merge intervals

↓

Repeat until all intervals processed

↓

Return merged intervals

Intervals problems usually start by sorting intervals, then merging or comparing overlaps step-by-step.

Execution Sample

DSA Typescript

const intervals = [[1,3],[2,6],[8,10],[15,18]];
intervals.sort((a,b) => a[0] - b[0]);
const merged = [];
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]);
  }
}

This code merges overlapping intervals by sorting and then combining them step-by-step.

Execution Table

Step	Operation	Current Interval	Merged List Before	Action	Merged List After	Visual State
1	Sort intervals	[1,3],[2,6],[8,10],[15,18]	[]	Sort by start time	[]	[1,3] -> [2,6] -> [8,10] -> [15,18] -> null
2	Initialize merged	[1,3]	[]	Add first interval	[[1,3]]	[1,3] -> null
3	Check overlap	[2,6]	[[1,3]]	2 <= 3 overlap, merge	[[1,6]]	[1,6] -> null
4	Check overlap	[8,10]	[[1,6]]	8 > 6 no overlap, add	[[1,6],[8,10]]	[1,6] -> [8,10] -> null
5	Check overlap	[15,18]	[[1,6],[8,10]]	15 > 10 no overlap, add	[[1,6],[8,10],[15,18]]	[1,6] -> [8,10] -> [15,18] -> null
6	End	N/A	[[1,6],[8,10],[15,18]]	All intervals processed	[[1,6],[8,10],[15,18]]	[1,6] -> [8,10] -> [15,18] -> null

💡 All intervals processed, merged list contains combined intervals without overlap.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
intervals	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]
merged	[]	[[1,3]]	[[1,6]]	[[1,6],[8,10]]	[[1,6],[8,10],[15,18]]	[[1,6],[8,10],[15,18]]
current interval	N/A	[1,3]	[2,6]	[8,10]	[15,18]	N/A

Key Moments - 3 Insights

Why do we sort intervals before merging?

Sorting ensures intervals are in order by start time, so we can merge overlaps by comparing only the last merged interval (see execution_table step 1 and 3). Without sorting, overlaps could be missed.

Why do we compare current interval start with last merged interval end?

This check (step 3 and 4) tells if intervals overlap. If current start is less or equal to last merged end, they overlap and must be merged. Otherwise, current interval is separate and added as new.

How does merging intervals update the merged list?

When intervals overlap, we update the end of last merged interval to the max end of both intervals (step 3). This keeps merged intervals non-overlapping and combined.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the merged list after merging?

A [[1,3]]

B [[2,6]]

C [[1,6]]

D [[1,3],[2,6]]

💡 Hint

Check the 'Merged List After' column at step 3 in execution_table.

At which step does the condition for no overlap first occur?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Action' column in execution_table where it says 'no overlap, add'.

If the intervals were not sorted, how would the merged list after step 3 change?

A It might miss merging some overlapping intervals

B It would be the same as [[1,6]]

C It would be empty

D It would contain duplicates

💡 Hint

Refer to key_moments about why sorting is important before merging.

Concept Snapshot

Intervals problems often require sorting intervals by start time first.
Then, iterate intervals and merge if overlapping.
Check overlap by comparing current start with last merged end.
Merge by updating last merged end to max end.
Add non-overlapping intervals directly.
This pattern simplifies handling ranges and scheduling tasks.

Full Transcript

Intervals are common in problems like scheduling or ranges. The key is to sort intervals by their start time first. Then, we keep a merged list starting with the first interval. For each next interval, we check if it overlaps with the last merged interval by comparing start and end times. If they overlap, we merge by updating the end time. If not, we add the interval as new. This step-by-step merging ensures no overlaps remain. Sorting is crucial to avoid missing overlaps. This pattern helps solve many interval-related problems 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