IncidentsCalculation.java

/**
 *The IncidentsCalculation calculates the incidents percentage for a given query and all the incidents.
 * 
 * @author Xidong Liu <xliu035@gmail.com>
 */

import java.util.*;

public class IncidentsCalculation {
  
	/*
	 * For a query and a list of incidents, getting the incidents percentage in the queried period.
	 */
	public double getIncidentsPercentage(Interval query, ArrayList<Interval> incidents) {
		double incidentsTime = 0;
		double queryTime = query.end - query.start;;
		double percentage = 0;
		
		if (query == null || queryTime <= 0 || incidents == null || incidents.isEmpty())
			return percentage;
		
		ArrayList<Interval> mergedIncidents = merge(incidents);		
		ArrayList<Interval> overlapped = getOverlappedInterval(query, mergedIncidents);

		for (Interval interval : overlapped) {
			incidentsTime += interval.end - interval.start;
		}
		
		percentage = incidentsTime / queryTime;
		return percentage;
	}
	
	/*
	 * For a query and a list of incidents, getting the overlapped interval between the query and the incidents.
	 */
	private ArrayList<Interval> getOverlappedInterval(Interval query, ArrayList<Interval> incidents) {
		ArrayList<Interval> res = new ArrayList<Interval>();
		
		if (query == null || query.start >= query.end || incidents == null || incidents.isEmpty())
			return res;
		
		for (Interval interval : incidents) {
			if (query.end <= interval.start)
				break;
			if (query.start >= interval.end)
				continue;
			int start = Math.max(query.start, interval.start);
			int end = Math.min(query.end, interval.end);	
			res.add(new Interval(start, end));
		}
		return res;
	}
	
	/*
	 * For a list of intervals, sorting the intervals in lexicographic order and merging the overlapped intervals in the list.
	 */
	private ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<Interval>();
	    if (intervals == null || intervals.isEmpty())
	        return res;
	    Comparator<Interval> comparator = new Comparator<Interval>() {
	        @Override
	        public int compare(Interval i1, Interval i2) {
	            if (i1.start < i2.start)
	                return -1;
	            else if (i1.start > i2.start)
	                return 1;
	            else {
	                if (i1.end < i2.end)
	                    return -1;
	                else if (i1.end > i2.end)
	                    return 1;
	                else
	                    return 0;
	            }
	        }
	    };
	    Collections.sort(intervals, comparator);
        Interval pre = new Interval();
	    for (Interval cur : intervals) {
	    	if (cur.start >= cur.end)
	    		continue;
	        if (res.isEmpty()) {
                pre = cur;
	            res.add(cur);
	        } else {
	            if (pre.end >= cur.start) {
	                pre.end = Math.max(pre.end, cur.end);
	            } else {
                    pre = cur;
	                res.add(cur);
	            }
	        }
	    }
	    return res;
    }
	
	public static void main(String[] args) {
		IncidentsCalculation incidentsCalculation = new IncidentsCalculation();
		Interval query = new Interval();
		ArrayList<Interval> incidents = new ArrayList<Interval>();
		double expected;
		
		//Test Example 1
		expected = 0.6;
		query = new Interval(10, 20);
		incidents = new ArrayList<Interval>();
		incidents.add(new Interval(8, 15));
		incidents.add(new Interval(18, 19));
		System.out.println("Expected " + expected + " Output " + incidentsCalculation.getIncidentsPercentage(query, incidents));

		//Test Example 2
		expected = 0.5;
		query = new Interval(40, 70);
		incidents = new ArrayList<Interval>();
		incidents.add(new Interval(50, 60));
		incidents.add(new Interval(50, 62));
		incidents.add(new Interval(50, 65));
		System.out.println("Expected " + expected + " Output " + incidentsCalculation.getIncidentsPercentage(query, incidents));
		
		//Test valid query and valid incidents
		query = new Interval(0, 10);
		incidents = new ArrayList<Interval>();
		incidents.add(new Interval(0, 50));
		incidents.add(new Interval(20, 30));
		incidents.add(new Interval(51, 52));
		System.out.println("Output " + incidentsCalculation.getIncidentsPercentage(query, incidents));		
		
		//Test invalid query
		query = new Interval(-10, 10);
		query = new Interval(100, 10);
		incidents = new ArrayList<Interval>();
		incidents.add(new Interval(0, 50));
		incidents.add(new Interval(50, 60));
		System.out.println("Output " + incidentsCalculation.getIncidentsPercentage(query, incidents));
		
		//Test invalid incidents
		query = new Interval(0, 50);
		incidents = new ArrayList<Interval>();
		incidents.add(new Interval(0, 10));
		incidents.add(new Interval(50, 30));
		incidents.add(new Interval(40, 50));
		System.out.println("Output " + incidentsCalculation.getIncidentsPercentage(query, incidents));
	}
}