CareerCup

I can propose NlogN solution. Place all begins and ends of intervals to array, mark beg as +1 end as -1. Sort them by time component. Then iterate over and accumulate ones. Interval with maximum sum will be interval of max overlap.

Given [0, 3] [3, 6], do they overlap? If yes, the output should be [3, 3]?

And given [0, 3] [4, 6] [2, 5], the output is {[0, 3], [2, 5]} {[4, 6], [2, 5]} ?

Look on wikipedia for interval tree -- exists for solving this very same problem. Similar to that is Segment Tree. Both are tricky to build but very efficient in answering the question. Not sure what expectation of interviewers in this particular case.

For discussion of the first part, prepend stackoverflow to: questions/4446112/search-for-interval-overlap-in-list-of-intervals

I just assume
- the method should return all possible sets of intervals which overlap
- [0, 3] [3, 6] are regarded as overlapped

For the follow up question, I would need the definition of "maximum"
Is it for the length of overlap or the count of intervals which overlap?
In either case, I can get it easily from the returned sets.

import java.util.*;

public class JE19 {
	// Given a set of intervals (time in seconds) find the set of intervals that overlap. 
	// Follow-up: what if we were to find the interval with maximum overlap
	// input : array of class Interval
	// output : array of array of class Interval (overlap)
	// interval is inclusive. [1, 3] [3, 6] --> overlapped
	public static void main(String[] args) {
		ArrayList<Interval> input = new ArrayList<>();
		input.add(new Interval(0, 3));
		input.add(new Interval(4, 6));
		input.add(new Interval(2, 5));
		//input.add(new Interval(3, 8));
		
		ArrayList<ArrayList<Interval>> res = findSetOfIntervalsOverlapped(input);
		for(ArrayList<Interval> outer : res) {
			for(Interval inter : outer) {
				System.out.print(inter);
			}
			System.out.println();
		}
	}
	static class Interval {
		int min, max;
		Interval(int min, int max) {
			this.min = min;
			this.max = max;
		}
		
		public String toString() {
			return "[" + min + ", " + max + "]";
		}
		
	}
	
	public static ArrayList<ArrayList<Interval>> findSetOfIntervalsOverlapped(ArrayList<Interval> list) {
		int n = list.size();
		ArrayList<ArrayList<Interval>> res = new ArrayList<>();
		
		for(int i=0; i<n; i++) {
			int size = res.size();
			for(int j=0; j<size; j++) {
				if(isOverlapped(list.get(i), res.get(j))) {
					if(res.get(j).size() == 1) {
						ArrayList<Interval> newitem = new ArrayList<>();
						newitem.add(res.get(j).get(0));						
						newitem.add(list.get(i));
						res.add(newitem);
					}
					else {
						res.get(j).add(list.get(i));
					}
				}
			}
			ArrayList<Interval> newitem = new ArrayList<>();
			newitem.add(list.get(i));
			res.add(newitem);
		}
		
		int m = res.size();
		for(int i=0; i<m; i++) {
			if(res.get(i).size() == 1) {
				res.remove(i);
				i--;
				m--;
			}
		}
		
		return res;
	}
	
	public static boolean isOverlapped(Interval inter, ArrayList<Interval> list) {
		boolean bOverlapped = true;
		for(Interval i : list) 
			if(inter.min > i.max || inter.max < i.min) {
				bOverlapped = false;
				break;
			}
		return bOverlapped;
	}
}

sort the data on the start time in ascending order. Use each given end point to find out the overlapped intervals.