In a calendar where multiple events can be scheduled over the same time window, print a list of all conflicting time windows along with the event IDs that are conflicting.

PrintConflictingIntervals.java

/**
 * In a calendar where multiple events can be scheduled over the same time window, print a list of all 
 * conflicting time windows along with the event IDs that are conflicting. All times are in 24 hour format.
 * Example:
 * Input:
 * Event 1 : 2014-01-01 9:45 - 2014-01-01 10:30
 * Event 2 : 2014-01-01 10:00 - 2014-01-01 10:30
 * Event 3 : 2014-01-01 10:20 - 2014-01-01 10:45
 * 
 * Output:
 * 2014-01-01 10:00 - 2014-01-01 10:20 {1,2}
 * 2014-01-01 10:20 - 2014-01-01 10:30 {1,2,3}
 * */
import java.util.*;

public class PrintConflictingIntervals {

  private List<Pair<Pair<Date, Integer>, Boolean>> scheduledEvents = new ArrayList<>();
  
  public PrintConflictingIntervals() {
  }

  // Should allow multiple events to be scheduled over the same time window.
  public void schedule(Event event) {
    if(event != null){
        scheduledEvents.add(
        		new Pair<Pair<Date, Integer>, Boolean>(
        				new Pair<Date, Integer>(event.getStartDate(), event.getId()),
        				true));
        scheduledEvents.add(
        		new Pair<Pair<Date, Integer>, Boolean>(
        				new Pair<Date, Integer>(event.getEndDate(), event.getId()),
        				false));
    }
  }

  // Gets all the conflicted times in sorted order
  public List<ConflictedTimeWindow> findConflictedTimeWindow() {
    // Sort all events by date
	Collections.sort(scheduledEvents, new Comparator<Pair<Pair<Date, Integer>, Boolean>>(){
    	@Override
    	public int compare(final Pair<Pair<Date, Integer>, Boolean> o1, final Pair<Pair<Date, Integer>, Boolean> o2){
    		if(o1.getFirst().getFirst().compareTo(o2.getFirst().getFirst()) == 0){
    			return o1.getFirst().getSecond().compareTo(o2.getFirst().getSecond());
    		}
    		return o1.getFirst().getFirst().compareTo(o2.getFirst().getFirst());
    	}
    });
	List<ConflictedTimeWindow> output = new ArrayList<ConflictedTimeWindow>();
    Set<Integer> ongoing = new HashSet<>();
    ongoing.add(scheduledEvents.get(0).getFirst().getSecond()); // Add first event Id
    Date start = scheduledEvents.get(0).getFirst().getFirst();
    for(int i = 1; i < scheduledEvents.size(); i++){
    	if(scheduledEvents.get(i).getSecond()){
    		// If start time, add this event to ongoing and ongoing events to this event's conflicted list
    		// and update start time
    		ongoing.add(scheduledEvents.get(i).getFirst().getSecond());
    		start = scheduledEvents.get(i).getFirst().getFirst();
    		// Add this conflict and update the start time only if there is no possibility that next start time is same as current
    		if(ongoing.size() > 1 && !start.equals(scheduledEvents.get(i+1).getFirst().getFirst())){
    			Set<Integer> temp = new HashSet<Integer>();
    			temp.addAll(ongoing);
    			ConflictedTimeWindow res = new ConflictedTimeWindow(start, scheduledEvents.get(i + 1).getFirst().getFirst(), temp); 
    			output.add(res);
    			start = scheduledEvents.get(i + 1).getFirst().getFirst();
    		}
    	}
    	else{
    		// If end time, then add this conflict if not already added and update the start time and remove this from
    		// the ongoing event list
    		if(ongoing.size() > 1 && !start.equals(scheduledEvents.get(i).getFirst().getFirst())){
    			Set<Integer> temp = new HashSet<Integer>();
    			temp.addAll(ongoing);
    			ConflictedTimeWindow res2 = new ConflictedTimeWindow(start, scheduledEvents.get(i).getFirst().getFirst(), temp); 
    			output.add(res2);
    			start = scheduledEvents.get(i).getFirst().getFirst();
    		}
    		ongoing.remove(scheduledEvents.get(i).getFirst().getSecond());
    	}
    }
    return output;
  }

  public static class ConflictedTimeWindow{
    private final Date startDate;
    private final Date endDate;
    private final Set<Integer> conflictedEventIds;

    public ConflictedTimeWindow(Date startDate, Date endDate, Set<Integer> conflictedEventIds) {
      this.startDate = startDate;
      this.endDate = endDate;
      this.conflictedEventIds = conflictedEventIds;
    }

    public Date getStartDate() {
      return startDate;
    }

    public Date getEndDate() {
      return endDate;
    }

    public Set<Integer> getConflictedEventIds() {
      return conflictedEventIds;
    }

    @Override
    public String toString() {
      return "ConflictedTimeWindow{" +
          "startDate=" + startDate +
          ", endDate=" + endDate +
          ", conflictedEventIds=" + conflictedEventIds +
          '}';
    }
  }

  public static class Event{
    private final int id;
    private final Date startDate;
    private final Date endDate;

    public Event(int id, Date startDate, Date endDate) {
      this.id = id;
      this.startDate = startDate;
      this.endDate = endDate;
    }

    public int getId() {
      return id;
    }
    
    public Date getStartDate() {
      return startDate;
    }

    public Date getEndDate() {
      return endDate;
    }
    
    @Override
    public String toString() {
      return "Event{" +
          "id=" + id +
          ", startDate=" + startDate +
          ", endDate=" + endDate +
          '}';
    }
  }

  public static class Pair<L,R> {
	    private L first;
	    private R second;
	    public Pair(L l, R r){
	        this.first = l;
	        this.second = r;
	    }
	    public L getFirst(){ return first; }
	    public R getSecond(){ return second; }
	    public void setFirst(L l){ this.first = l; }
	    public void setSecond(R r){ this.second = r; }
  }
  
  public static void main(String[] args) {
    PrintConflictingIntervals pci = new PrintConflictingIntervals();

    pci.schedule(new Event(1, new Date(114, 0, 1, 10, 0), new Date(114, 0, 1, 11, 0))); // 2014-01-01 10:00 - 11:00
    pci.schedule(new Event(2, new Date(114, 0, 1, 11, 0), new Date(114, 0, 1, 12, 0))); // 2014-01-01 11:00 - 12:00
    pci.schedule(new Event(3, new Date(114, 0, 1, 12, 0), new Date(114, 0, 1, 13, 0))); // 2014-01-01 12:00 - 13:00

    pci.schedule(new Event(4, new Date(114, 0, 2, 10, 0), new Date(114, 0, 2, 11, 0))); // 2014-01-02 10:00 - 11:00
    pci.schedule(new Event(5, new Date(114, 0, 2, 9, 30), new Date(114, 0, 2, 11, 30))); // 2014-01-02 09:30 - 11:30
    pci.schedule(new Event(6, new Date(114, 0, 2, 9, 45), new Date(114, 0, 2, 10, 30))); // 2014-01-02 09:45 - 10:30
    pci.schedule(new Event(7, new Date(114, 0, 2, 8, 30), new Date(114, 0, 2, 12, 30))); // 2014-01-02 08:30 - 12:30
    pci.schedule(new Event(8, new Date(114, 0, 2, 10, 20), new Date(114, 0, 2, 10, 40))); // 2014-01-02 10:20 - 10:40

    pci.schedule(new Event(9, new Date(114, 0, 3, 10, 0), new Date(114, 0, 3, 11, 0))); // 2014-01-03 10:00 - 11:00
    pci.schedule(new Event(10, new Date(114, 0, 3, 9, 30), new Date(114, 0, 3, 10, 30))); // 2014-01-03 09:30 - 10:30
    pci.schedule(new Event(11, new Date(114, 0, 3, 9, 45), new Date(114, 0, 3, 10, 45))); // 2014-01-03 09:45 - 10:45
    pci.schedule(new Event(12, new Date(114, 0, 3, 10, 0), new Date(114, 0, 3, 10, 35))); // 2014-01-03 10:00 - 10:35
    pci.schedule(new Event(13, new Date(114, 0, 3, 10, 0), new Date(114, 0, 3, 11, 0))); // 2014-01-03 10:00 - 11:00
    List<ConflictedTimeWindow> conflictedTimeWindows = pci.findConflictedTimeWindow();
    for(ConflictedTimeWindow ctw : conflictedTimeWindows)
    	System.out.println(ctw);
    
//    Output should be something like -
//    ConflictedTimeWindow{startDate=Thu Jan 02 09:30:00 PST 2014, endDate=Thu Jan 02 09:45:00 PST 2014, conflictedEventIds=[5, 7]}
//    ConflictedTimeWindow{startDate=Thu Jan 02 09:45:00 PST 2014, endDate=Thu Jan 02 10:00:00 PST 2014, conflictedEventIds=[5, 6, 7]}
//    ConflictedTimeWindow{startDate=Thu Jan 02 10:00:00 PST 2014, endDate=Thu Jan 02 10:20:00 PST 2014, conflictedEventIds=[4, 5, 6, 7]}
//    ConflictedTimeWindow{startDate=Thu Jan 02 10:20:00 PST 2014, endDate=Thu Jan 02 10:30:00 PST 2014, conflictedEventIds=[4, 5, 6, 7, 8]}
//    ConflictedTimeWindow{startDate=Thu Jan 02 10:30:00 PST 2014, endDate=Thu Jan 02 10:40:00 PST 2014, conflictedEventIds=[4, 5, 7, 8]}
//    ConflictedTimeWindow{startDate=Thu Jan 02 10:40:00 PST 2014, endDate=Thu Jan 02 11:00:00 PST 2014, conflictedEventIds=[4, 5, 7]}
//    ConflictedTimeWindow{startDate=Thu Jan 02 11:00:00 PST 2014, endDate=Thu Jan 02 11:30:00 PST 2014, conflictedEventIds=[5, 7]}
//    ConflictedTimeWindow{startDate=Fri Jan 03 09:45:00 PST 2014, endDate=Fri Jan 03 10:00:00 PST 2014, conflictedEventIds=[10, 11]}
//    ConflictedTimeWindow{startDate=Fri Jan 03 10:00:00 PST 2014, endDate=Fri Jan 03 10:30:00 PST 2014, conflictedEventIds=[9, 10, 11, 12, 13]}
//    ConflictedTimeWindow{startDate=Fri Jan 03 10:30:00 PST 2014, endDate=Fri Jan 03 10:35:00 PST 2014, conflictedEventIds=[9, 11, 12, 13]}
//    ConflictedTimeWindow{startDate=Fri Jan 03 10:35:00 PST 2014, endDate=Fri Jan 03 10:45:00 PST 2014, conflictedEventIds=[9, 11, 13]}
//    ConflictedTimeWindow{startDate=Fri Jan 03 10:45:00 PST 2014, endDate=Fri Jan 03 11:00:00 PST 2014, conflictedEventIds=[9, 13]}

  }

}