Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Merge Intervals (medium)

Problem Statement

Given a list of intervals, merge all the overlapping intervals to produce a list that has only mutually exclusive intervals.

Example 1:

Intervals: [[1,4], [2,5], [7,9]]
Output: [[1,5], [7,9]]
Explanation: Since the first two intervals [1,4] and [2,5] overlap, we merged them into one [1,5].

Example 2:

Intervals: [[6,7], [2,4], [5,9]]
Output: [[2,4], [5,9]]
Explanation: Since the intervals [6,7] and [5,9] overlap, we merged them into one [5,9].

Example 3:

Intervals: [[1,4], [2,6], [3,5]]
Output: [[1,6]]

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

is the Interval class working in the back despite being commented out in the solution?

Show 1 reply
A

Anonymous

· 2 years ago


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

#  def print_interval(self):
#    print("[" + str(self.start) + ", " + str(self.end) + "]", end='')

class Solution:
  def merge(self, intervals):
    result = []

    # sort the intervals in-order to merge them
    intervals.sort(key = lambda i: i.start)
    
    for interval in intervals:
      if not result: 
        result.append(interval)
      else:
        # [a, b] is the previous interval in the result array
        # [c, d] is the current internal from the loop
        a, b = result[-1].start, result[-1].end
        c, d = interval.start, interval.end
        # if overlap
        if c <= b:
          # merge then update the result array
          merged = Interval(a, max
A

Anonymous

· 3 years ago

I am getting an error using python, trying to sort the list:

TypeError: 'Interval' object is not subscriptable

when I use either:

intervals.sort(key=lambda i: i[0])

OR

sorted(intervals, key=lambda i: i[0])

I can do this operation in my personal terminal with no issues

Show 1 reply
A

Anonymous

· 3 years ago

public List<Interval> merge(List<Interval> intervals) {
    List<Interval> mergedIntervals = new LinkedList<Interval>();
    // TODO: Write your code here 
    if(intervals.size()<2)
      return intervals;
    Interval l;
    Interval r;
    mergedIntervals.add(0, intervals.get(0));
    intervals.remove(0);
    int ls;
    int le;
    Iterator<Interval> intervalItr = intervals.iterator();
    while (intervalItr.hasNext()) {
      l=mergedIntervals.get(0);
      r=intervalItr.next();
      if(overlap(l, r)){
        ls = l.start;
        le = l.end;
        mergedIntervals.remove(0);
        mergedIntervals.add(0, new Interval(Math.min(ls, r.start), Math.max(le, r.end)));
      }
      else
        mergedIntervals.add(new Interval(r.start, r.end));
    }
    
    return mergedInter
Show 1 reply
A

Anonymous

· 3 years ago

Anyone have implemented this problem in C#?I tried but facing some problem , logic is quite complex

A

Anonymous

· 4 years ago

As described in the title, I don't understand why we add the last interval to mergedIntervals outside the loop? Don't we also evaluate the last interval in intervals inside the for loop? Thank you!

Show 1 reply
A

Anonymous

· 4 years ago

This is a wildly over complicated way of handling this in JavaScript! Why would you use process.stdout.write? I am very disappointed with this answer.

A

Anonymous

· 4 years ago

The C++ code in this course is generally lacking, but this example was particularly over-complicated. While I can understand certain design decisions, there are a couple others that really should not have been made. And a few times, outdated practices are employed.

The biggest offender in this lesson is the Interval itself. It should be a struct, and the constructor should utilize the initialization section for more efficient, and more concise code.

My next gripe is the expression(s) *intervalItr++. The dereference and increment are close enough in precedence that I have to look it up every now and again. While what it accomplishes in a single expression is neat, it hurts readability. A similar tack can be used to simplify the while loop while increasing readability and eliminating

Show 3 replies
A

Anonymous

· 4 years ago

I seem to be missing something when observing the solution. I understand when interval 1 is compared to interval 2, and I understand when interval 2 is compared to interval 3. But I do not see how interval 1 would be compared to interval 3. Am I missing something?

Show 1 reply
A

Anonymous

· 4 years ago

type at the last comment line for python. Its 'Interval' not 'Internval'

for i in range(1, len(intervals)): interval = intervals[i] if interval.start

Show 1 reply

Reading Progress

0%

Vote for new content