Grokking the Coding Interview: Patterns for Coding 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!
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