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

Mental Model

Intervals represent ranges of values, like time slots or segments, that often overlap or need merging to solve real problems.

Analogy: Imagine booking meeting rooms where each meeting has a start and end time. You want to know if meetings clash or how many rooms you need.

Time line:
|----|----|----|----|----|----|----|----|
  1    2    3    4    5    6    7    8

Intervals:
[1 -> 3]
      [2 -> 5]
           [6 -> 8]

Dry Run Walkthrough

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

Goal: Show how overlapping intervals cause problems and why merging helps.

Step 1: Look at first interval [1,3]

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

Why: Start with the earliest interval to compare others against.

Step 2: Check if second interval [2,5] overlaps with first [1,3]

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

Why: Intervals overlap if start of second is before or equal to end of first.

Step 3: Merge overlapping intervals into [1,5]

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

Why: Merging simplifies overlapping intervals into one continuous range.

Step 4: Check if third interval [6,8] overlaps with merged [1,5]

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

Why: No overlap because 6 > 5, so keep separate.

Result:

[1 -> 5]  [6 -> 8]  (merged intervals showing no overlaps)

Annotated Code

DSA Javascript

class Interval {
  constructor(start, end) {
    this.start = start;
    this.end = end;
  }
}

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

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

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

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i].start <= current.end) {
      // overlap detected
      current.end = Math.max(current.end, intervals[i].end); // merge
    } else {
      merged.push(current); // no overlap, save current
      current = intervals[i]; // move to next
    }
  }
  merged.push(current); // add 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 time to process in order

let current = intervals[0];

start with first interval as current to compare others

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

check if next interval overlaps with current

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

merge overlapping intervals by extending end

merged.push(current);

save non-overlapping interval before moving on

merged.push(current);

add last interval after loop ends

Output

[1, 5]

[6, 8]

Complexity Analysis

Time: O(n log n) because sorting intervals takes O(n log n) and merging takes O(n)

Space: O(n) because we store merged intervals in a new list

vs Alternative: Naive approach checks every pair for overlap O(n^2), merging after sorting is more efficient

Edge Cases

empty intervals list

returns empty list without error

DSA Javascript

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

intervals with no overlaps

returns original intervals sorted

DSA Javascript

if (intervals[i].start <= current.end) { ... } else { merged.push(current); current = intervals[i]; }

intervals fully contained inside others

merges into larger interval correctly

DSA Javascript

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 merging or counting overlaps solves them efficiently.

Common Mistakes

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

Mistake: Merging intervals incorrectly by not updating the end properly
Fix: Update current interval's end to the max end of overlapping intervals

Summary

It explains why intervals appear often and how merging overlapping intervals solves many problems.

Use it when dealing with ranges like meeting times, bookings, or segments that may overlap.

The key insight is sorting intervals first lets you merge overlaps in one pass efficiently.

Practice

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

easy

A. Because intervals never overlap in any problem

B. Because intervals are always sorted by default

C. Because intervals only deal with single numbers

D. Because many real-world problems involve ranges or periods of time

Solution

1. Step 1: Understand what intervals represent

   Intervals represent ranges, such as time periods or numeric ranges, which are common in real-world scenarios.

2. Step 2: Connect intervals to problem patterns

   Many problems require managing overlapping or merging these ranges, making intervals a common pattern.

3. Final Answer:

   Because many real-world problems involve ranges or periods of time -> Option D

4. Quick Check:

   Intervals = ranges in real life [OK]

Hint: Think about real-life ranges like meetings or bookings [OK]

Common Mistakes:

• Assuming intervals are always sorted
• Thinking intervals never overlap
• Believing intervals are single points

2. Which of the following is the correct syntax to represent an interval in JavaScript as an object with start and end properties?

easy

A. const interval = (1, 5);

B. const interval = [start: 1, end: 5];

C. const interval = {start: 1, end: 5};

D. const interval = {1, 5};

Solution

1. Step 1: Recall JavaScript object syntax

   Objects use curly braces with key-value pairs like {key: value}.

2. Step 2: Match the correct interval representation

   The interval with start and end keys is correctly written as {start: 1, end: 5}.

3. Final Answer:

   const interval = {start: 1, end: 5}; -> Option C

4. Quick Check:

   Object syntax = {key: value} [OK]

Hint: Use curly braces and key-value pairs for objects [OK]

Common Mistakes:

• Using square brackets for objects
• Using parentheses for objects
• Missing keys in object syntax

3. What will be the output of the following JavaScript code?

const intervals = [
  {start: 1, end: 3},
  {start: 2, end: 6},
  {start: 8, end: 10}
];

const merged = [];
intervals.sort((a, b) => a.start - b.start);

for (const interval of intervals) {
  if (!merged.length || merged[merged.length - 1].end < interval.start) {
    merged.push(interval);
  } else {
    merged[merged.length - 1].end = Math.max(merged[merged.length - 1].end, interval.end);
  }
}

console.log(merged);

medium

A. [{start: 1, end: 6}, {start: 8, end: 10}]

B. [{start: 1, end: 3}, {start: 2, end: 6}, {start: 8, end: 10}]

C. [{start: 1, end: 10}]

D. [{start: 2, end: 6}, {start: 8, end: 10}]

Solution

1. Step 1: Sort intervals by start

   Intervals are sorted as [{1,3}, {2,6}, {8,10}].

2. Step 2: Merge overlapping intervals

   First interval added. Second overlaps with first, so merge to {1,6}. Third does not overlap, so added as is.

3. Final Answer:

   [{start: 1, end: 6}, {start: 8, end: 10}] -> Option A

4. Quick Check:

   Merged intervals = [{1,6}, {8,10}] [OK]

Hint: Sort by start, then merge overlapping intervals [OK]

Common Mistakes:

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

4. The following code is intended to merge overlapping intervals but has a bug. What is the bug?

const intervals = [
  {start: 1, end: 4},
  {start: 3, end: 5}
];

const merged = [];
for (const interval of intervals) {
  if (!merged.length || merged[merged.length - 1].end < interval.start) {
    merged.push(interval);
  } else {
    merged[merged.length - 1].end = Math.max(merged[merged.length - 1].end, interval.end);
  }
}

console.log(merged);

medium

A. Using Math.min instead of Math.max in merging

B. Intervals are not sorted before merging

C. Pushing intervals without checking overlap

D. Not initializing merged as an array

Solution

1. Step 1: Check if intervals are sorted

   The code does not sort intervals before merging, which can cause incorrect merges.

2. Step 2: Understand impact of missing sort

   Without sorting, overlapping intervals may not be adjacent, so merging logic fails.

3. Final Answer:

   Intervals are not sorted before merging -> Option B

4. Quick Check:

   Sort intervals first [OK]

Hint: Always sort intervals by start before merging [OK]

Common Mistakes:

• Forgetting to sort intervals
• Using wrong Math function
• Ignoring overlap checks

5. Given a list of intervals representing booked meeting times, how would you find the minimum number of meeting rooms required to hold all meetings without overlap?

hard

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

B. Sort intervals by end time, merge all intervals, count merged intervals

C. Count intervals with the same start time only

D. Use a stack to push all intervals and pop when overlap occurs

Solution

1. Step 1: Sort intervals by start time

   Sorting helps process meetings in chronological order.

2. Step 2: Use a min-heap to track earliest ending meeting

   Min-heap stores end times; if a meeting starts after earliest end, reuse room; else add room.

3. Step 3: Count maximum rooms used simultaneously

   The heap size at any time shows rooms needed; max size is minimum rooms required.

4. Final Answer:

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

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 instead of counting overlaps
• Ignoring meeting end times
• Using stack instead of min-heap