Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Insert Interval

Problem Statement

Given a list of non-overlapping intervals sorted by their start time, insert a given interval at the correct position and merge all necessary intervals to produce a list that has only mutually exclusive intervals.

Example 1:

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,6]
Output: [[1,3], [4,7], [8,12]]
Explanation: After insertion, since [4,6] overlaps with [5,7], we merged them into one [4,7].

Example 2:

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,10]
Output: [[1,3], [4,12]]

.....

.....

.....

Like the course? Get enrolled and start learning!
R

Richard Yuan

· 4 years ago

To confirm, we can follow another similar approach to "Merge Intervals" with sorting removed by inserting the new interval into the list of intervals based on start value. So insert into the first index where new_interval[start] is greater than intervals[i][start]? We then perform the rest of the "Merge Intervals" logic to avoid having to set new_interval[start] = min(new_interval[start], intervals[i][start]).

Show 2 replies
H

hj3yoo

· 4 years ago

Why does the condition on the first while loop of the solution use a non-inclusive unequal operator, whereas the second loop uses an inclusive one? Shouldn't you merge two intervals if the end of the first interval is equal to the start of the next interval?

Show 1 reply
A

Athanasios Petsas

· 4 years ago

We can change a bit the Insert Interval solution to make it in-place (constant space). Code in C++ here: {code} static vector insert (vector & intervals, Interval given) { if (intervals.size() == 0) { // or intervals.empty() intervals.push_back(given); return intervals; } // iterate throught all the intervals int i=0; while (i < intervals.size() && intervals[i].end < given.start) { // skip non-overlapping intervals with given i++; }

// merge all intervals that overlap with given while (i < intervals.size() && intervals[i].start

B

brigadirden

· 3 years ago

But since the given list is sorted, we should try to come up with a solution better than O(n log).

This is really confusing - we should try, but in the end nothing said about it and we ending up with time complexity O(n).

Show 2 replies
D

davemednikov

· 3 years ago

These variables are defined in the solution code however they are not used for anything. This is sort of confusing because they follow a similar naming pattern to the start and end properties of each interval. Also it causes the space complexity to be increased.

The solution still passes when those variables are removed.

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

#class Interval:
#  def __init__(self, start, end):
#    self.start = start
#    self.end = end

class Solution:
  
  def insert(self, intervals, new_interval):
    merged = []
    for interval in intervals:
      if new_interval: # if we have not found a position for the new interval 'not null'
        
        # new interval < than interval
        if new_interval.end < interval.start:
          merged.append(new_interval)
          merged.append(interval)
          new_interval = None
        
        # new interval > than the interval
        elif new_interval.start > interval.end:
          merged.append(interval)
         
         # they can be merged
        else:
          merged.append(Interval(min(new_interval.start, interval.start), max(new_interval.end, interval.
R

raphael_1st

· 2 years ago

Hello,

I have a question about this algorithm when we have merging intervals that come before the newly inserted interval (passing the redundancy). For example, if we have,

input = [[1,3], [2,4],[7,9],[8,12]], new interval = [6, 10]

the result should be,

[[1,4], [6,12]]

I can't understand, with the current algorithm in this example, how we get the [1,4]. If I understood correctly, because we are not merging the intervals that come before the new insertion, the interval will be instead [2,4].

In other words, the final result will be,

[[2,4], [6,12]], instead of [[1,4], [6,12]].

Is this example valid or am I missing something?

W

wchang778

· 2 years ago

as the official solution just use get(i) to at out items in List<Interval>, but if the underlying implementation is a LinkedList this could explode to N^2.

Vinh Duc Nguyen Le

Vinh Duc Nguyen Le

· a year ago

first binary search find left - smallest start interval overlap

second binary search find right - biggest start interval overlap?