Find the point where maximum intervals overlap
https://www.geeksforgeeks.org/find-the-point-where-maximum-intervals-overlap/
http://www.cnblogs.com/Gryffin/p/7468676.html
Given an array of intervals in a line consisting of start and end points [[s1,e1],[s2,e2],...] (si < ei), find any point that is covered by most intervals.
https://www.geeksforgeeks.org/find-the-point-where-maximum-intervals-overlap/
Consider a big party where a log register for guest’s entry and exit times is maintained. Find the time at which there are maximum guests in the party. Note that entries in register are not in any order.
Example :
Input: arrl[] = {1, 2, 9, 5, 5} exit[] = {4, 5, 12, 9, 12} First guest in array arrives at 1 and leaves at 4, second guest arrives at 2 and leaves at 5, and so on. Output: 5 There are maximum 3 guests at time 5.
Below is a Simple Method to solve this problem.
1) Traverse all intervals and find min and max time (time at which first guest arrives and time at which last guest leaves)
2) Create a count array of size ‘max – min + 1’. Let the array be count[].
3) For each interval [x, y], run a loop for i = x to y and do following in loop.
count[i – min]++;
count[i – min]++;
4) Find the index of maximum element in count array. Let this index be ‘max_index’, return max_index + min.
Above solution requires O(max-min+1) extra space. Also time complexity of above solution depends on lengths of intervals. In worst case, if all intervals are from ‘min’ to ‘max’, then time complexity becomes O((max-min+1)*n) where n is number of intervals.
An Efficient Solution is to use sorting n O(nLogn) time. The idea is to consider all events (all arrivals and exits) in sorted order. Once we have all events in sorted order, we can trace the number of guests at any time keeping track of guests that have arrived, but not exited.
Given an array of intervals in a line consisting of start and end points [[s1,e1],[s2,e2],...] (si < ei), find any point that is covered by most intervals.
public static class Interval { int start; int end; Interval(int start, int end) { this.start = start; this.end = end; } } public int getDensity(List<Interval> intervals) { int[] starts = new int[intervals.size()]; int[] ends = new int[intervals.size()]; for (int i = 0; i < starts.length; i++) { starts[i] = intervals.get(i).start; ends[i] = intervals.get(i).end; } Arrays.sort(starts); Arrays.sort(ends); int end = 0; int ans = 0; for (int i = 0; i < starts.length; i++) { if (starts[i] >= ends[end]) { end++; } else { ans = starts[i]; } } return ans; }