Wednesday, November 5, 2014

Facebook: Maximum number of overlapping intervals

Given n intervals [si, fi], find the maximum number of overlapping intervals
http://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/
A wrong solution:
public class Solution {
    public int maxIntervals(List<Interval> intervals) {
        if (intervals == null || intervals.size() == 0) {
            return 0;
        }
        
        if (intervals.size() == 1) {
            return 1;
        }
        
        int count = 1;
        int max = 1;
        
        // Sort the intervals based on start
        Collections.sort(intervals, new IntervalComparator());
        
        Interval prev = intervals.get(0);
        
        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (curr.start <= prev.end) {
                int left = Math.min(curr.start, prev.start);
                int right = Math.max(curr.end, prev.end);
                prev = new Interval(left, right);
                
                count++;
                max = Math.max(count, max);
            } else {
                prev = curr;
                count = 1;
            }
        }
        return max;
    }
    
    private class IntervalComparator implements Comparator<Interval> {
        public int compare(Interval a, Interval b) {
            return a.start - b.start;
        }
    }
}

Why it is wrong:

Take an example, e.g. [1, 7], [2, 3] [4, 5]. The solution above will get the result of 3, which actually should be 2 instead. 

The correct solution:
public class Solution {
    public int numOverLaps(List<Integer> start, List<Integer> end) {
        if (start == null || start.size() == 0 || end == null || end.size() == 0) {
            return 0;
        }
        
        if (start.size() != end.size()) {
            return 0;
        }
        
        Collections.sort(start);
        Collections.sort(end);
        
        int startP = 0;
        int endP = 0;
        
        int numActive = 0;
        int numOverlap = 0;
        
        while (startP < start.size() && endP < end.size()) {
            if (start.get(startP) < end.get(endP)) {
                numActive++;
                numOverlap = Math.max(numOverlap, numActive);
                startP++;
            } else {
                numActive--;
                endP++;
            }
        }
        return numOverlap;
    }

  public static void main(String[] args) {
    Solution sol = new Solution();

    List<Integer> start = new ArrayList<Integer>();
    List<Integer> end = new ArrayList<Integer>();

    start.add(1);
    start.add(2);
    start.add(5);
    start.add(4);

    end.add(3);
    end.add(4);
    end.add(6);
    end.add(7);

    int result = sol.numOverLaps(start, end);

    System.out.println("Result is " + result);
  }
}

1 comment: