CareerCup

Think of it as a room and the intervals are times when a person is in the room. You are looking for time when max number of people are in a room. Note: I am assuming open intervals.

So sort the points, and traverse in ascending order. As an event occurs (person joins, left endpoint or person leaves, right end point), update the counts accordingly.

def get_max_overlap(intervals):
  
	endpoints = []
	left = None
	count = 0
	for interval in intervals:
		endpoints.append((interval[0], True, interval))
		endpoints.append((interval[1], False, interval))
  
	endpoints.sort()
  
	count = 0
	max_count = 0
	cur_intervals = {}
	max_intervals = {}
	for endpoint in endpoints:	
		interval = endpoint[2]
		is_left = endpoint[1]
		if is_left:
			count += 1
			cur_intervals[interval] = count
			if count > max_count:
				max_count = count
				max_intervals = cur_intervals.copy()
		else:
			del cur_intervals[interval]
			count -= 1
    			
	return max_intervals.keys()
  
   
def get_intervals(points_list):
	intervals = []
	left = None
	count = 0
	for point in points_list:
		count += 1
		if count % 2 == 0:
			intervals.append((left, point))
		else:
			left = point
	return intervals
  
  
def print_intervals(msg, intervals, scale = 3):
	sorted_intervals = sorted(intervals, key = lambda x: x[0])
	print msg, sorted_intervals
  
	for interval in sorted_intervals:
		left = interval[0]
		right = interval[1]
		left_indent = left*scale -2
		if left > 10:
			left_indent -= 1
		w = (right-left)*scale
		print " "*left_indent,left,"-"*w,right
  
def show_overlaps(points_list):
	intervals = get_intervals(points_list)
	overlap = get_max_overlap(intervals)
	print_intervals("Input", intervals)
	print ""
	print_intervals("Maximum Overlap", overlap)
  
def main():
	show_overlaps([0,5,2,9,8,10,6,9])
	show_overlaps([1,20,2,8,3,15,8,12,14,17,19,20,2,22])
  
if __name__ == "__main__":
	main()

Input [(0, 5), (2, 9), (6, 9), (8, 10)]
 0 --------------- 5
     2 --------------------- 9
                 6 --------- 9
                       8 ------ 10
  
Maximum Overlap [(2, 9), (6, 9), (8, 10)]
     2 --------------------- 9
                 6 --------- 9
                       8 ------ 10

  
Input [(1, 20), (2, 8), (2, 22), (3, 15), (8, 12), (14, 17), (19, 20)]
  1 --------------------------------------------------------- 20
     2 ------------------ 8
     2 ------------------------------------------------------------ 22
        3 ------------------------------------ 15
                       8 ------------ 12
                                        14 --------- 17
                                                       19 --- 20
  
Maximum Overlap [(1, 20), (2, 8), (2, 22), (3, 15)]
  1 --------------------------------------------------------- 20
     2 ------------------ 8
     2 ------------------------------------------------------------ 22
        3 ------------------------------------ 15

This is a problem of finding the number of platform required on a railway station given the train arrival and departure times.

[a1,d1], [a2,d2], [a3,d3]....
create two sorted array - one for arrival and another for departure.

initialize the number of platform required = 0;
i and j the counters for arrival and departure list; initialized to 0;

for all a[i] in the arrival sorted list
{

increment the number of platform required by 1;
if d[j] < a[i] then
{
decrement the number of platform required by 1;
j++;
}
i++;
}

number of platform required is the max_interval;

Doesn't [2,9] overlap with [0, 5] and similarly for others?

I think you can sort the intervals by the right endpoint which will result in
[0, 5]
[2, 9]
[6, 9]
[8, 10] in this case. Now you know that the left endpoint of the rightmost interval will be <= or > to the right endpoint of the previous one. If it's the former, we increment the counter and proceed to the previous interval until we find the interval whose right endpoint is smaller than the left endpoint. If it's the latter case, you exclude that interval and continue the process for the rest of the case. Sorting takes O(nlogn) and takes linear time to search for the maximally overlapping interval.

The question is unclear. Do we return the interval/count which intersects with most intervals or we are looking for maximum overlap (i.e. a set of intervals which intersect each other).

Basically, if you create a graph of intervals (adjacency determined by interval intersection) are you looking for maximum degree or maximum clique?

The typically asked question is for maximum clique.

if it means the max number in a certain interval, then can be done by sorting on the left point, then binary search the right point in the list, and keep the end position for each interval in an array, so in one pass we'll get the result. time complexity o(nlgn) space o(n)

if it means the interval which overlaps most number of intervals, we need sort twice. one is by the left point, the other on the right point. similar idea, just count twice to get each interval's overlapping number. still nlgn

for overlapping mean the element within 1 interval lies in other.then for each interval u can check that the lower bound of other interval is greater than the first interval and upperbound is less than the upper bound of first interval..
complexity 0(n^2).

public class maxIntervals {
	public static boolean findIntervals(int a1, int b1, int a2, int b2) {
		if ((b1 < a2) || (a1 > b2))
			return false;
		return true;
	}

	public static void main(String[] args) {
		maxIntervals ob1 = new maxIntervals();
		int size = 4;

		// int interval[][] = new int[size][size];
		int interval[][] = { { 0, 5 }, { 2, 9 }, { 6, 9 }, { 8, 10 }};
		int intervalCount[] = new int[size];
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				
				if (!(i == j)) {
					if (findIntervals(interval[i][0], interval[i][1],
							interval[j][0], interval[j][1])) {
						int key = 0;
						key = intervalCount[i];
						key++;
						intervalCount[i] = key++;
					}
				}
			}
		}
		for (int i = 0; i < size; i ++ ) {
			System.out.println(intervalCount[i]);
		}
	}

}

#include<stdio.h>
int main()
{
int arr[8]={0,5,2,9,8,10,6,9};
int table[11]={0};
int i,sizeArray,max,temp1,temp2;
max=0xFFFF;
sizeArray=sizeof(arr)/sizeof(int);
/* for(i=0;i<sizeArray;i++)
{
if(max<arr[i])
max=arr[i];
}
*/
for(i=0;i<sizeArray;i++)
{
temp1=arr[i];
temp2=arr[++i];
while(temp1<=temp2)
{
table[temp1]=table[temp1]+1;
temp1++;
}
}
printf("Table\n");
for(i=0;i<=10;i++)
printf("%d ",table[i]);
max=table[0];
for(i=1;i<=10;i++)
{
if(max<table[i])
{
max=table[i];
}
}
printf("\nMax=%d",max);
return 0;
}

#include<stdio.h>
int main()
{
    int arr[8]={0,5,2,9,8,10,6,9};
    int table[11]={0};
    int i,sizeArray,max,temp1,temp2;
    max=0xFFFF;
    sizeArray=sizeof(arr)/sizeof(int);
   /* for(i=0;i<sizeArray;i++)
    {
        if(max<arr[i])
            max=arr[i];
    }
    */
    for(i=0;i<sizeArray;i++)
    {
        temp1=arr[i];
        temp2=arr[++i];
        while(temp1<=temp2)
        {
            table[temp1]=table[temp1]+1;
            temp1++;
        }
    }
    printf("Table\n");
    for(i=0;i<=10;i++)
        printf("%d ",table[i]);
    max=table[0];
    for(i=1;i<=10;i++)
    {
        if(max<table[i])
        {
            max=table[i];
        }
    }
    printf("\nMax=%d",max);
    return 0;
}

I think this can be easier using interval tree.

Store input into String array. String[] intervals = { "0-5", "2-9", "8-10", "6-9" };
Here is the code

public static void overlapping(String[] intervals) {
        boolean[] overlaps = new boolean[100];

        int rangeStart = 0;
        int rangeEnd = 0;
        List<Integer> ll = new ArrayList<Integer>();
        for (String interval : intervals) {
            int start = Integer.parseInt(interval.split("-")[0]);
            int end = Integer.parseInt(interval.split("-")[1]);
            if (rangeEnd != 0) {
                ll.add(rangeEnd + rangeStart);
            }
            rangeStart = 0;
            rangeEnd = 0;
            boolean rangeFlag = false;
            for (int i = start; i <= end; i++) {
                if (!overlaps[i]) {
                    overlaps[i] = true;
                } else {
                    if (!rangeFlag) {
                        rangeStart = i;
                        ll.add(rangeStart);
                        rangeFlag = true;
                    }
                    rangeEnd++;
                }
            }
        }

        System.out.println(ll.size() / 2);
    }