Grokking 75: Top Coding Interview Questions

0% completed

​

Solution: Merge Intervals

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

Adam Sweeney

· 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
Laurensius Hans Santoso

Laurensius Hans Santoso

· 3 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
Spencer Lan

Spencer Lan

· 2 years ago

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

Show 1 reply
P

Patrick Reid

· 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.

E

eric

· 4 years ago

Wouldn't the time complexity be O(N + logN) instead? Because the sorting is done outside the loop which incurs a O(logN) time, and afterward we're just looping through each interval which is O(N). Since the sorting is not done within the loop, it would be an addition instead of multiplication wouldn't it?

Show 1 reply
C

Cj

· 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
J

Jason

· 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
S

seth

· 5 years ago

I think the result should be usable, whereas for example in JS the result is only usable as a string, since it can't be reasonably processed as an array due to integer keys.

Using an array of objects like [{2:5}, {1:4}, {7:9}] etc for i/o, a simple 15 line function without a helper class is sufficient, and the result allows for further processing.

Show 1 reply
S

sweetykumari

· 3 years ago

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

Satya Pandya

Satya Pandya

· 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