Insert Interval into Sorted List in DSA Javascript - Build from Scratch

Insert Interval into Sorted List

📖 Scenario: You are managing a calendar that stores busy time slots as intervals. Each interval is a pair of numbers representing start and end times. The calendar keeps these intervals sorted and non-overlapping.Now, you want to add a new busy time slot to this calendar. But if the new slot overlaps with existing ones, you need to merge them to keep the calendar clean and sorted.

🎯 Goal: Build a program that inserts a new interval into a sorted list of non-overlapping intervals and merges any overlapping intervals.

📋 What You'll Learn

Create a variable called intervals with the exact array of intervals: [[1, 3], [6, 9]]

Create a variable called newInterval with the exact array: [2, 5]

Write a function called insertInterval that takes intervals and newInterval as parameters and returns the updated list with merged intervals

Use a for loop with variable interval to iterate over intervals

Print the result of calling insertInterval(intervals, newInterval)

💡 Why This Matters

🌍 Real World

Calendars, booking systems, and time management apps often need to insert and merge time slots efficiently.

💼 Career

Understanding interval merging is useful for software engineers working on scheduling, resource allocation, and data range queries.

1

Create the initial intervals list

Create a variable called intervals and set it to the array [[1, 3], [6, 9]]

DSA Javascript

# Your code here

Hint

Use const intervals = [[1, 3], [6, 9]]; to create the list.

2

Create the new interval to insert

Create a variable called newInterval and set it to the array [2, 5]

DSA Javascript

const intervals = [[1, 3], [6, 9]];
# Your code here

Hint

Use const newInterval = [2, 5]; to create the new interval.

3

Write the function to insert and merge intervals

Write a function called insertInterval that takes parameters intervals and newInterval. Use a for loop with variable interval to iterate over intervals. Merge overlapping intervals and return the updated list.

DSA Javascript

const intervals = [[1, 3], [6, 9]];
const newInterval = [2, 5];

// Write function insertInterval below
# Your code here

Hint

Use a for loop with const interval to count intervals before newInterval, then process the remaining intervals to merge overlaps.

4

Print the updated intervals after insertion

Print the result of calling insertInterval(intervals, newInterval) using console.log

DSA Javascript

const intervals = [[1, 3], [6, 9]];
const newInterval = [2, 5];

function insertInterval(intervals, newInterval) {
    const result = [];
    let beforeCount = 0;
    for (const interval of intervals) {
        if (interval[1]  mergedEnd) {
            break;
        }
        mergedStart = Math.min(mergedStart, intv[0]);
        mergedEnd = Math.max(mergedEnd, intv[1]);
    }
    result.push([mergedStart, mergedEnd]);
    result.push(...remaining.slice(j));
    return result;
}

// Print the updated intervals
# Your code here

Hint

Use console.log(insertInterval(intervals, newInterval)); to print the updated intervals.

Practice

1. What is the main goal when inserting a new interval into a sorted list of non-overlapping intervals?

easy

A. To add the new interval at the end without checking overlaps

B. To merge overlapping intervals and keep the list sorted

C. To remove all intervals that come before the new interval

D. To sort the intervals again after insertion without merging

Solution

1. Step 1: Understand the problem context

   We have a sorted list of intervals with no overlaps, and we want to insert a new interval.

2. Step 2: Identify the correct approach

   We must merge any intervals that overlap with the new one and keep the list sorted.

3. Final Answer:

   To merge overlapping intervals and keep the list sorted -> Option B

4. Quick Check:

   Insert interval = merge and sort [OK]

Hint: Merge overlapping intervals to keep list sorted after insertion [OK]

Common Mistakes:

• Inserting without merging overlaps
• Appending without sorting
• Removing unrelated intervals

2. Which of the following is the correct syntax to insert an interval [3,5] into a JavaScript array named intervals?

easy

A. intervals.push([3,5])

B. intervals.insert([3,5])

C. intervals.add([3,5])

D. intervals.append([3,5])

Solution

1. Step 1: Recall JavaScript array methods

   JavaScript arrays use push() to add elements at the end.

2. Step 2: Match method to syntax

   push() is correct; insert(), add(), and append() are not valid JavaScript array methods.

3. Final Answer:

   intervals.push([3,5]) -> Option A

4. Quick Check:

   Use push() to add elements in JS arrays [OK]

Hint: Use push() to add elements to JavaScript arrays [OK]

Common Mistakes:

• Using insert() which is not a JS array method
• Using add() or append() from other languages
• Forgetting to add as an array element

3. What is the output of the following code?

const intervals = [[1,2],[5,6]];
const newInterval = [3,5];
function insertInterval(intervals, newInterval) {
  const result = [];
  let i = 0;
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    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;
}
console.log(insertInterval(intervals, newInterval));

medium

A. [[1,2],[5,6],[3,5]]

B. [[1,2],[3,5],[5,6]]

C. [[1,6]]

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

Solution

1. Step 1: Process intervals before newInterval

   Intervals before newInterval are [[1,2]] because 2 < 3, so push [1,2].

2. Step 2: Merge overlapping intervals

   Intervals overlapping with newInterval are [5,6] because 5 <= 5. Merge [3,5] and [5,6] to get [3,6].

3. Step 3: Add merged interval and remaining intervals

   Push merged [3,6]. No intervals left after merging.

4. Final Answer:

   [[1,2],[3,6]] -> Option D

5. Quick Check:

   Merged intervals = [[1,2],[3,6]] [OK]

Hint: Merge intervals overlapping newInterval, keep others as is [OK]

Common Mistakes:

• Not merging overlapping intervals
• Adding newInterval multiple times
• Incorrectly ordering intervals after merge

4. Identify the bug in this code snippet that inserts a new interval into a sorted list:

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

medium

A. The newInterval is pushed before merging

B. The first while condition should use < instead of <=

C. The second while condition should use <= instead of <

D. The result array is not initialized

Solution

1. Step 1: Analyze the second while loop condition

   The second loop merges overlapping intervals. It uses intervals[i][0] < newInterval[1], which misses intervals starting exactly at newInterval[1].

2. Step 2: Correct the condition

   Change < to <= to include intervals starting at newInterval[1] for proper merging.

3. Final Answer:

   The second while condition should use <= instead of < -> Option C

4. Quick Check:

   Use <= to merge intervals starting at newInterval[1] [OK]

Hint: Use <= to include intervals starting exactly at newInterval end [OK]

Common Mistakes:

• Using < instead of <= in merge condition
• Pushing newInterval too early
• Not initializing result array

5. Given intervals = [[1,3],[6,9]] and newInterval = [2,5], what is the correct output after inserting and merging intervals?

hard

A. [[1,5],[6,9]]

B. [[1,3],[2,5],[6,9]]

C. [[2,5],[6,9]]

D. [[1,9]]

Solution

1. Step 1: Identify intervals before newInterval

   Interval [1,3] overlaps with newInterval [2,5] because 3 >= 2, so no intervals come before without overlap.

2. Step 2: Merge overlapping intervals

   Merge [1,3] and [2,5] to get [1,5]. Interval [6,9] does not overlap and stays as is.

3. Final Answer:

   [[1,5],[6,9]] -> Option A

4. Quick Check:

   Merged intervals = [[1,5],[6,9]] [OK]

Hint: Merge all overlapping intervals including newInterval [OK]

Common Mistakes:

• Not merging overlapping intervals
• Adding newInterval without merging
• Merging unrelated intervals