CareerCup

take an array of size 50 init it with all ZEROs
make an entry as 1 of the interval for all given interval
count number of 1 in the array & divide it by 50......

If you dont sort this will be O(n) time

@Mike: Then you might have to consider multiple intervals for merging... and might become quadratic.

Care to elaborate?

There is no need to use stack. We just have to know where is the end of the intervals which has been added so far. Here is algo:
1) Sort intervals according to 'start' coordinate;
2) Add first interval to the sum
3) Set 'current end' = firstInter.end
4) Iterate over remaining intervals and check 3 conditions. If new interval is
4.1) fully included in the already calculated intervals - then skip
4.2) is partially included e.g [1,7][5,10] - the add only remaining part and update 'current end'
4.3) excluded - add whole interval -and update 'current end'
5) result = sum/length
O(n log n) time, O(1) space.
Code:

package akamai;

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

public class VideoInterval {

    public static class Interval {
	Integer start;
	Integer end;

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

	public static void sort(List<Interval> intervals) {

	    Collections.sort(intervals, new Comparator<Interval>() {
		@Override
		public int compare(Interval o1, Interval o2) {
		    return o1.start.compareTo(o2.start);
		}

	    });
	}
    }

    /**
     * @param args
     */
    public static void main(String[] args) {

	List<Interval> intervals = new ArrayList<VideoInterval.Interval>();
	// 1-7, 10-15, 5-11, 20-25
	intervals.add(new Interval(1, 7));
	intervals.add(new Interval(10, 15));
	intervals.add(new Interval(5, 11));
	intervals.add(new Interval(20, 25));
	Interval.sort(intervals);

	Interval first = intervals.get(0);
	int sum = first.end - first.start;
	int currentEnd = first.end;
	for (int i = 1; i < intervals.size(); i++) {
	    Interval next = intervals.get(i);
	    if (next.start < currentEnd) {
		// fully included - skip
		if (next.end <= currentEnd) {
		    continue;
		    // partially included - add remaining part
		} else {
		    sum += next.end - currentEnd;
		    currentEnd = next.end;
		}
		// excluded - add whole interval
	    } else {
		sum += next.end - next.start;
		currentEnd = next.end;
	    }
	}

	System.out.println((float) (sum + 1) / 50); // +1 include last minute -
						    // [1 - 7] is 7 not 6
    }

}

This will have Time Complexity of O(n). But this will have memory complexity of O(total). The time complexity is gud but the memory complexity is horrible. Thus I would recommend the solution with merge sorting first and then simple comparisons but the two consecutive range.

So helpful. Thanks.