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

• Peilonrayz: I added the programming-challenge tag as you completed a programming challenge. However I've removed the community-challenge tag, as these are programming challenges hosted by us at Code Review.
• Stingy: You commented out the Interval class, but the class Solution depends on it. Is this a mistake?
• Imus: I've checked the linked site. The interval class is defined outside of scope, it's commented to show what it looks like so you can use it correctly.
• Bill K: We actually use classes like this all the time. I recommend creating a "holder" for intervals (Ours is called Profile because it's time based) that keeps them in order using a HashMap. As you add one Interval to the holder it will automatically insert into the correct location and merge with overlapping intervals.. then you never have to deal with more than merging a single interval into a list at a time; Also better code. Note that it MAY help to create "Not intervals" (Intervals indicated as empty) to ensure that the entire range is filled--helped simplify our code to be continuous.
• Anirudh Thatipelli: Thanks, I had forgotten to add that, @Peilonrayz

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.

• Stingy: But by removing the temporary variables mStart and mEnd, you need to modify the method parameter newInterval, which might not be desirable.
• Anirudh Thatipelli: Thanks a lot, @Imus for pointing these mistakes. My code seemed very messy and I missed many edge cases before getting the correct answer.

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.

• Imus: Hmm, good second point. I put that in when I still had a bug in the while conditions. Makes me wonder if I should edit that out now ...
• Anirudh Thatipelli: Thanks, I had missed this point. I wanted the interval to be arranged in ascending order.