Leetcode 56 Merge Intervals and 57 Insert Interval

Leetcode 56 Merge Intervals and 57 Insert Interval

Leetcode 56 Merge Intervals
Edit Merge Intervals on GitHub

The problem description is as follow:

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

The definition of interval is as follow:

public class Interval {
    int start;
    int end;
    Interval() { start = 0; end = 0; }
    Interval(int s, int e) { start = s; end = e; }
}

Think first, the given collection of intervals are not sorted yet. It will be so simple if they are sorted according to the start point.

Thus we will need a customized comparator to sort intervals according to the start point of interval:

class IntervalComparator implements Comparator<Interval> {
    public int compare(Interval i1, Interval i2) {
        return i1.start - i2.start;
    }
}

Besides, List<Interval> class is only an abstract class, you will need to instantiate it with ArrayList<Interval> or LinkedList<Interval> etc:

List<Interval> result = new ArrayList<Interval>()

Here comes the full solution:

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <= 1)
            return intervals;
        // sort intervals by using self-defined Comparator
        Collections.sort(intervals, new IntervalComparator());
        List<Interval> result = new ArrayList<Interval>();
        Interval prev = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (prev.end >= curr.start) {
                // merged case
                Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end));
                prev = merged;
            } else {
                result.add(prev);
                prev = curr;
            }
        }
        result.add(prev);
        return result;
    }
}
 
class IntervalComparator implements Comparator<Interval> {
    public int compare(Interval i1, Interval i2) {
        return i1.start - i2.start;
    }
}

Analysis:

The sort of collections is O(nlog(n)) and the traverse of sorted collection of is O(n). Thus the solution’s time efficiency is O(nlog(n)+n) = O(nlogn).

Leetcode 57 Insert Interval
Edit Insert Interval on GitHub

The problem description is as follow:

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

Assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

This is basically a transform of the previous question, even much simpler. Since the collection of intervals is already sorted and guaranteed not to overlap, we just have to put the new interval in the right place according to it’s start point and run the merge process the same as previous problem.

The full solution is as follow:

public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> result=new ArrayList<Interval>();
        if (newInterval==null){
            return intervals;
        }
        if (intervals==null||intervals.size()==0){
            result.add(newInterval);
            return result;
        }   
        for (Interval current: intervals){
            // case 1
            if (current.start>newInterval.end){
                result.add(newInterval);
                newInterval=current;
            }
            // case 3
            else if (current.end<newInterval.start){ 
                result.add(current); 
            }
            // case 2
            else{
                newInterval.start=Math.min(newInterval.start, current.start);
                newInterval.end=Math.max(newInterval.end, current.end);
            }
        }      
        result.add(newInterval);
        return result;
    }
}

The following graph from programcreek will make things clearer: