Why Intervals Are a Common Problem Pattern in DSA Javascript - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to merge overlapping intervals.

DSA Javascript

function mergeIntervals(intervals) {
  intervals.sort((a, b) => a[[1]] - b[[1]]);
  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]);
    }
  }
  return merged;
}

Drag options to blanks, or click blank then click option'

A0

B1

Clength

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by end time instead of start time.

Using incorrect index for start time.

We sort intervals by their start time, which is at index 0 in each interval array.

2fill in blank

medium

Complete the code to check if two intervals overlap.

DSA Javascript

function isOverlap(interval1, interval2) {
  return interval1[1] > interval2[[1]] && interval2[1] > interval1[0];
}

Drag options to blanks, or click blank then click option'

A1

B2

C0

Dlength

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong index for start or end.

Using >= instead of > which may cause incorrect overlap detection.

We check if the end of the first interval is after the start of the second interval (index 0).

3fill in blank

hard

Fix the error in the code to insert a new interval into a list of non-overlapping intervals.

DSA Javascript

function insertInterval(intervals, newInterval) {
  const result = [];
  let i = 0;
  while (i < intervals.length && intervals[i][1] < newInterval[[1]]) {
    result.push(intervals[i]);
    i++;
  }
  while (i < intervals.length && 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);
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }
  return result;
}

Drag options to blanks, or click blank then click option'

A0

B1

Clength

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with wrong index of newInterval.

Mixing up start and end indices.

We compare the end of current intervals with the start of newInterval, which is at index 0.

4fill in blank

hard

Fill both blanks to create a dictionary of intervals keyed by their start time and filtered by intervals longer than 2 units.

DSA Javascript

const filteredIntervals = intervals.reduce((acc, interval) => {
  if (interval[[1]] - interval[[2]] > 2) {
    acc[interval[0]] = interval;
  }
  return acc;
}, {});

Drag options to blanks, or click blank then click option'

A1

B0

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping start and end indices.

Using same index for both blanks.

We subtract start (index 0) from end (index 1) to get interval length.

5fill in blank

hard

Fill all three blanks to create a map of interval lengths keyed by the interval's start time, only for intervals starting after 5.

DSA Javascript

const intervalLengths = intervals.reduce((map, interval) => {
  if (interval[[1]] > 5) {
    map[interval[[2]]] = interval[[3]] - interval[0];
  }
  return map;
}, {});

Drag options to blanks, or click blank then click option'

A0

C1

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices for start or end.

Mixing up keys and values in the map.

We check start time at index 0, use it as key, and calculate length as end (index 1) minus start (index 0).

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