Friday, December 12, 2014

Add interval to an array of intervals

Merge sorted, non-overlapping list of intervals with another interval.
e.g., Intervals[(1,3), (5,10), (12,30)] + addOne[9,31] = [(1,3), (5,31)]

Update an much neater code. And correct the empty intervals case.


 public class Interval {
      int start;
      int end;
      Interval() { start = 0; end = 0; }
      Interval(int s, int e) { start = s; end = e; }
  }
 
public class InsertInterval {
    public ArrayList insert(ArrayList intervals, Interval newInterval) {
        ArrayList rst = new ArrayList();
        if (intervals == null || newInterval == null)
            return intervals;
            
        Collections.sort(intervals, new IntervalComparator());
        int insert_pos = 0;
        for (Interval intv : intervals)
        {
            if (intv.end < newInterval.start)
            {
                rst.add(intv);
                insert_pos++;
            }
            else if (intv.start > newInterval.end)
                rst.add(intv);
            else
            {
                newInterval.start = Math.min(intv.start, newInterval.start);
                newInterval.end = Math.max(intv.end, newInterval.end);
            }
        }
        rst.add(insert_pos, newInterval);
        return rst;
    }
    private class IntervalComparator implements Comparator
    {
        public int compare(Interval a, Interval b)
        {
             return a.start - b.start;
        }
    }

Start with two conditions:
1. the end point of the added one is smaller than the start point of the first element in the array or the start point of the added one is larger than the end point of the last element in the array. In this case, we simply add the addOne to the top or the bottom of the array, respectively.
2. addOne should be merged into the middle of the array;
In this case, we need to merge the overlapped intervals by finding the start and end point. And add the rest of the intervals to the result list.



import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;


public class AddInterval {
 public ArrayList add(ArrayList intervals, Interval addOne)
 {
  if (intervals == null || intervals.size() == 0)
   return null;
  Collections.sort(intervals, new IntervalComparator());
  //Two non-overlap boundary cases
  if (addOne.start > intervals.get(intervals.size() - 1).end)
  {
   intervals.add(addOne);
   return intervals;
  }
  if (addOne.end < intervals.get(0).start)
  {
   intervals.add(0, addOne);
   return intervals;
  }
  ArrayList rst = new ArrayList();
  int index = 0;
  //skip all intervals that are "smaller" than addOne
  while (index < intervals.size() && intervals.get(index).end < addOne.start)
  { 
   rst.add(intervals.get(index));
   index++;
   continue;
  }
  Interval tmp = new Interval();
  //find the start point to add
  if (intervals.get(index).start < addOne.start)
   tmp.start = intervals.get(index).start;
  else
   tmp.start = addOne.start;
  //find the end point
  while (index < intervals.size() && intervals.get(index).end < addOne.end)
   index++;
  //if addOne.end is larger than the "end" of the last interval, simply take addOne.end and return 
  if (index == intervals.size() && intervals.get(index - 1).end < addOne.end)
  {
   tmp.end = addOne.end;
   rst.add(tmp);
   return rst;
  }
  if(intervals.get(index).start <= addOne.end)
  {
   tmp.end = intervals.get(index).end;
   index++;
  }
  else
   //current interval is not merged with addOne and has not yet been added to rst
   tmp.end = addOne.end;
  rst.add(tmp);
  
  //add the rest of the intervals
  while (index < intervals.size())
  {
   rst.add(intervals.get(index));
   index++;
  }
  return rst;
 }
 
 private class IntervalComparator implements Comparator
 {
  public int compare(Interval a, Interval b)
  {
   return a.start - b.start;
  }
 }
}

1 comment:

  1. The development of artificial intelligence (AI) has propelled more programming architects, information scientists, and different experts to investigate the plausibility of a vocation in machine learning. Notwithstanding, a few newcomers will in general spotlight a lot on hypothesis and insufficient on commonsense application. IEEE final year projects on machine learning In case you will succeed, you have to begin building machine learning projects in the near future.

    Projects assist you with improving your applied ML skills rapidly while allowing you to investigate an intriguing point. Furthermore, you can include projects into your portfolio, making it simpler to get a vocation, discover cool profession openings, and Final Year Project Centers in Chennai even arrange a more significant compensation.


    Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account.

    ReplyDelete