CareerCup

Update: As the problem looks like it need a data structure like cache to hold elements and perform operations. LinkedHashMap may be suitable to implement this as insertion and deletion are easy on it.

My below code is written using ArrayList and I am creating a result list every time when insert request comes which is not optimal.

Previously:

Possibility-1: This problem is combination of merge intervals and insert intervals case if the problem says the problem start with list of unsorted intervals.

Possibility-2 : If the problem is to assume one interval comes at a time as input, then it is straight forward insert interval case.

Java Solution:

Interval object can be stored as below.

class Interval{
	int start;
	int end;
	public Interval(int start, int end){
		this.start = start;
		this.end = end;
	}
}

Key points:
1. As the question is not clear, if the intervals are sorted or not incase of more intervals as a preprocessing step.
We can take initial List of initial set of inputs and sort them and merge them and keep it ready.

This can be a preprocessor step.

Merge (preprocess step) can be like below

public List<Interval> merge(List<Interval> input){
	List<Interval> results = new ArrayList<Interval>();
        //sort the collection
	Collections.sort(input,(i,j) -> (i.start = j.start ? (i.end.compareTo(j.end)) : i.start.compareTo(j.start) );

	//Loop through sorted input and merge
	Interval previous = null;
        for(Interval curr: input){
            if(previous == null || previous.end < curr.start){ //non-overlap case
                if(previous !=null){
                    results.add(previous);
                }
                previous = new Interval(curr.start, curr.end);
            }else{
                previous.start = Math.min(previous.start, curr.start);
                previous.end = Math.max(previous.end, curr.end);
            }
        }
        //Very important to add below code to handle last previous interval
        if(previous != null){
            results.add(previous);
        }
        return results;
}

2. After step-1, for every new interval, it is a insert interval scenario (data is already sorted in step-1)

public List<Interval> insertAndMerge(List<Interval> input, Interval target){

        //handle single element cases here
        if(input.size()==0){
            return null;
        }else if(input.get(0).start>target.end || input.get(input.size()-1).end < target.start){ //no overlap
                input.add(target);
        }else{
            int result = insertAndMerge2(input, 0, input.size() - 1, target);
            if(result == -1){
                input.add(target);
            }
        }
        return input;
    }

We can use the Interval Data structure or segment tree data structure for this Problem....

We can use Interval Tree or Segment Tree Data Structure ...

Look up an interval O(1)
Insert a new, non-overlapping interval O(n)
Insert an interval that partially overlaps some existing interval(s) O(n + k) where `k` is the number of overlapping intervals.

function IntervalCache () {
	this.intervals = {}
}

IntervalCache.prototype.find = function (interval) {
	return this.intervals[interval.join(',')]
}

IntervalCache.prototype.insert = function (interval) {
	var intersections = []
	for (var key in this.intervals) {
		if (({}).hasOwnProperty.call(this.intervals, key)) {
			if ((interval[1] >= this.intervals[key][0] && interval[1] <= this.intervals[key][1]) ||
				(interval[0] >= this.intervals[key][0] && interval[0] <= this.intervals[key][1]) ||
				(interval[0] < this.intervals[key][0] && interval[1] > this.intervals[key][1])) {
				intersections.push(this.intervals[key])
				delete this.intervals[key]
			}
		}
	}
	if (intersections.length === 0) {
		this.intervals[interval.join(',')] = interval
		return
	}
	var min = interval[0]
	var max = interval[1]
	while (intersections.length) {
		interval = intersections.pop()
		if (interval[0] < min) {
			min = interval[0]
		}
		if (interval[1] > max) {
			max = interval[1]
		}
	}
	this.intervals[[min, max].join(',')] = [min, max]
}

var cache = new IntervalCache()
cache.insert([25,100])
cache.insert([250,550])
cache.insert([1000, 1200])
cache.insert([400, 700])
cache.insert([30, 60])

console.log(cache)

@srterpe: That should be O(1) look up of interval.

@sumit.polite Segment Tree cannot be modified so not a good structure for this.

Can be done with BST. Just keep the intervals sorted and also keep max field for node

public void MergeIntervals(List<Interval> Intervals)
        {
            foreach (var interval in Intervals.ToList())
            {

                if(ListOfInterval == null)
                {
                    ListOfInterval = new List<Interval>
                    {
                        new Interval(interval.Start, interval.End)
                    };
                }
                else
                {
                    foreach(var existingInterval in ListOfInterval.ToList())
                    {
                        if (interval.Start > existingInterval.Start && interval.End < existingInterval.End)
                        {
                            interval.IsDealt = true;
                            continue; // Within a existing range
                        }
                        else
                        if (interval.Start < existingInterval.Start && interval.End > existingInterval.End)
                        {
                            ListOfInterval.Remove(existingInterval);
                            ListOfInterval.Add(new Interval(interval.Start, interval.End));
                            interval.IsDealt = true;
                            break;
                        }
                        else
                        if (interval.Start > existingInterval.Start && interval.Start < existingInterval.End
                            ||
                            interval.End > existingInterval.Start && interval.End < existingInterval.End)
                        {
                            ListOfInterval.Remove(existingInterval);
                            ListOfInterval.Add(new Interval(
                                Math.Min(interval.Start, existingInterval.Start),
                                Math.Max(interval.End, existingInterval.End)
                                ));
                            interval.IsDealt = true;
                            break;
                        }
                        
                        
                    }
                    if (! interval.IsDealt)
                        ListOfInterval.Add(new Interval(interval.Start, interval.End));
                }

            }

}