Merge non overlapping intervals

Question

Merge Intervals

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

You may 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] would result in [1,5],[6,9].

Example 2:

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

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

Make sure the returned intervals are also sorted.

My approach:

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */

public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        int mStart = newInterval.start;
        int mEnd = newInterval.end;

        ArrayList<Interval> ans = new ArrayList<Interval>();
        Interval inter = new Interval();
        int tmp;

        //Check if interval is larger than the elements present in the array
        int count = 0;

        if( inter.start > inter.end)
            {
                tmp = inter.start;
                inter.start = inter.end;
                inter.end = tmp;
            }

        //Base case when intervals has 0 size
        if( intervals.size() == 0 )
            {
                ans.add(newInterval);
                return ans;
            }

        for( int i = 0; i < intervals.size(); i++ )
            {
                int chStart = intervals.get(i).start;
                int chEnd = intervals.get(i).end;

                //Check for overlap condition
                if( Math.max(chStart,mStart) > Math.min(chEnd, mEnd))
                    {
                        ans.add(intervals.get(i));
                        count++;
                    }

                //Condition for overlap
                else
                    {
                        inter.start = Math.min(mStart,chStart);
                        inter.end = Math.max(mEnd, chEnd);

                        mStart = inter.start;
                        mEnd = inter.end;

                        if(!ans.contains(inter))
                            {
                             ans.add(inter);
                            }
                    }
            }
            //Condition when interval is larger than all elements in array, insert interval
            //in final answer
            if( count == intervals.size())
                ans.add(newInterval);

            //Sorting the arraylist according to start time using an inner class
            //Helps in modularity
            Collections.sort(ans, new IntervalSort());

            //Time complexity: O(n)
            //Space complexity: O(n)

       /* for( int i = 0; i < intervals.size(); i++ )
            {
                int chStart = intervals.get(i).start;
                int chEnd = intervals.get(i).end;

                if( (chStart <= mStart) && (chEnd > mStart) )
                    {
                       inter.start = chStart;

                       for( int j = i + 1; j < intervals.size(); j++)
                        {
                            chStart = intervals.get(j).start;
                            chEnd = intervals.get(j).end;

                            if( (chStart <= mEnd) && (mEnd < chEnd) )
                                inter.end = chEnd;

                            ans.add(intervals.get(j));

                        }

                    }
            ans.add(intervals.get(i));  
            }*/
        return ans;    
    }
           class IntervalSort implements Comparator<Interval>
                {
                public int compare(Interval arr1, Interval arr2)
                    {
                        return arr1.start - arr2.start;
                    }
                }
}

The commented portion is an approach that I had tried before I settled for this newer one

I have these questions regarding my code:

1) How can I further optimize my code in time and space complexity?

2) Are there any grave java coding conventions that I have violated?

3) Is my code too redundant or am I using too many unnecessary variables?

4) How can I make sure that I don't miss out on any of the test cases?

Reference

Answer 1

Couple of things my IDE complained about:

• if without braces:

  if (count == intervals.size()) {
      ans.add(newInterval);
  }
  

• opening { should be on same line, not on a new one (fixed with hotkey to apply all java style conventions).

• for loop can be replaced with foreach

  for (Interval current : intervals) {
  

And while I was at it I also removed the variables to store start and end of an interval. You can access them directly instead.

I would also assume that creating a new interval would have it's start time before end time, so that tmp swapping part is unnecessary.

At this point the code looks like this:

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
    ArrayList<Interval> ans = new ArrayList<Interval>();
    //Base case when intervals has 0 size
    if (intervals.isEmpty()) {
        ans.add(newInterval);
        return ans;
    }

    Interval inter = new Interval();
    //Check if interval is larger than the elements present in the array
    int count = 0;
    for (Interval current : intervals) {
        if (Math.max(current.start, newInterval.start) > Math.min(current.end, newInterval.end)) {
            //no overlap
            ans.add(current);
            count++;
        } else {
            inter.start = Math.min(newInterval.start, current.start);
            inter.end = Math.max(newInterval.end, current.end);

            newInterval.start = inter.start;
            newInterval.end = inter.end;

            if (!ans.contains(inter)) {
                ans.add(inter);
            }
        }
    }
    //Condition when interval is larger than all elements in array, insert interval
    //in final answer
    if (count == intervals.size()) {
        ans.add(newInterval);
    }

    //Sorting the arraylist according to start time using an inner class
    //Helps in modularity
    Collections.sort(ans, new IntervalSort());

    return ans;
}

Note that I also moved the count and inter variables below the base case if check. You don't need them yet before this check.

With that out of the way let's look at the actual algorithm.

---

The question clearly states that we can assume a sorted input list. So I was a bit surprised that you have to sort the ans in the end. If you follow these 3 steps it should already be sorted:

1) add all intervals that end before the new one to the result
2) merge the new one with any overlapping interval. When no more intervals overlap, add the merged interval
3) add the remaining intervals

public static ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
    ArrayList<Interval> ans = new ArrayList<Interval>();
    //Base case when intervals has 0 size
    if (intervals.isEmpty()) {
        ans.add(newInterval);
        return ans;
    }

    //bad design of Interval class allows for invalid intervals.
    //turn it into a correct interval before proceeding.
    if(newInterval.start > newInterval.end){
        newInterval = new Interval(newInterval.end, newInterval.start);
    }

    int currentIndex = 0;
    while(currentIndex < intervals.size() && intervals.get(currentIndex).end < newInterval.start) {
        ans.add(intervals.get(currentIndex));
        currentIndex++;
    }
    while(currentIndex < intervals.size() && intervals.get(currentIndex).start <= newInterval.end) {
        newInterval = new Interval(Math.min(intervals.get(currentIndex).start, newInterval.start),
                Math.max(intervals.get(currentIndex).end, newInterval.end));
        currentIndex++;
    }
    ans.add(newInterval);
    while (currentIndex < intervals.size()) {
        ans.add(intervals.get(currentIndex++));
    }
    return ans;
}

It took a couple of tries to also get the edge cases to pass on the site. As I commented in the code I would expect only valid intervals in the first place. In an actual interview question I would explain this instead of handling it and suggest either fixing the Interval class or their prefered way of dealing with errors like this. (Fix it like I did here, throw an error, assume correct input anyway and mention in method documentation that invalid input may have unexpected results).

Note that I also keep creating new Intervals. This is because I would also make that class immutable in the first place. If you want to save some space you can just overwrite vallues of the newInterval instead of creating a new instance.

Answer 2

• if(inter.start > inter.end) {
      tmp = inter.start;
      inter.start = inter.end;
      inter.end = tmp;
  }
  

  This block is completely unnecessary, not only for the reasons that Imus mentioned. When you create an Interval with the no-argument constructor, then start and end will be set to 0, which means that this block will never be executed. Maybe you confused inter with newInterval, in which case Imus' reasoning applies.

• Also, you don't need to handle the special case of an empty original interval list separately, because it will be caught by

  if(count == intervals.size())
      ans.add(newInterval);
  

  anyway (in this case, count will be 0). This also applies to the last code sample in Imus' answer.