Given a set of busy time inter | CareerCup

Given a set of busy time inter | CareerCup
http://www.careercup.com/question?id=5739192933941248
Given a set of busy time intervals of two people as in a calendar, find the free time intervals of both the people so as to arrange a new meeting
input: increasing sequence of pair of numbers
per1: (1,5) (10, 14) (19,20) (27,30)
per2: (3,5) (12,15) (18, 21) (23, 24)
ouput: (6,9) (16,17) (22,22) (25,26)

We don't have to sort: just merge them first.
Merging works because we are searching for places in which nothing is scheduled. If even one of the individuals have something scheduled, then there isn't free time.

public static int[][] getFreeTimes(int[][] person1, int[][] person2){
 //merge
 int[][] list = merge(person1, person1);
 //do the rest
 ArrayList<int[]> results = new ArrayList<int[]>();
 int workingEnd = 1;
 for(int[] event : list){
  if(event[0] <= workingEnd){
   if(event[1] >= workingEnd){
    workingEnd = event[1]+1;
   }
  }
  else{
   results.add(new int[]{workingEnd, event[1]-1}); // should be event[0]-1
   workingEnd = event[1]+1;
  }
 }
 return results.toArray();
}

  for (int i = 0; i < sortedMeetings.size(); i++) {
   Meeting duration1 = null;
   Meeting duration2 = null;
   if (i < sortedMeetings.size() - 1) {
    duration1 = sortedMeetings.get(i);
    duration2 = sortedMeetings.get(i + 1);

    if (duration1.getEndTime() < duration2.getStartTime()) {
     freeSlots.add(new Meeting(duration1.getEndTime(), duration2.getStartTime()));
    }
   }
  }

//TODO: check the logic
https://github.com/andreytim/jafar/blob/master/problems/src/main/java/com/andreytim/jafar/problems/sortsearch/P717_IntervalArraysMergeGaps.java
https://www.quora.com/Given-a-set-of-busy-time-intervals-of-two-people-as-in-a-calendar-what-is-the-algorithmic-approach-to-find-the-free-time-intervals-of-both-the-people-so-as-to-arrange-a-new-meeting
Merge all the intervals(per1 + per2) in a single list of intervals. Sort the list using start time of the intervals as the key.

Now, merge the overlapping intervals. Now iterate over the list with merged overlapping intervals and check for the gaps between the intervals. The gaps will be the free time intervals.

1. void get_free_times(const vector<pair<int, int> > &per1, const vector<pair<int, int> > &per2)
2. {
3. int i;
4. int s, e;
6. vector<pair<int, int> > allintervals;
7. vector<pair<int, int> > merged;
8. pair<int, int> temp;
10. for(i=0; i<per1.size(); i++)
11. {
12. allintervals.push_back(make_pair(per1[i].first, per1[i].second));
13. }
14. for(i=0; i<per2.size(); i++)
15. {
16. allintervals.push_back(make_pair(per2[i].first, per2[i].second));
17. }
19. sort(allintervals.begin(), allintervals.end());
21. for(i=0; i<allintervals.size(); i++)
22. {
23. if(temp.first==0 && temp.second==0)
24. {
25. temp.first=allintervals[i].first;
26. temp.second=allintervals[i].second;
27. }
28. if(allintervals[i].first>=temp.first && allintervals[i].first<=temp.second)
29. {
30. temp.second=max(allintervals[i].second, temp.second);
31. }
32. else
33. {
34. merged.push_back(temp);
35. temp.first=allintervals[i].first;
36. temp.second=allintervals[i].second;
37. }
38. }
39. merged.push_back(temp);
41. for(i=0; i<merged.size()-1; i++)
42. {
43. s=merged[i].second+1;
44. e=0;
45. if(s<merged[i+1].first)
46. {
47. e=merged[i+1].first-1;
48. }
49. if(e)
50. {
51. cout<<"("<<s<<", "<<e<<")"<<endl;
52. }
53. }
54. }

Read full article from Given a set of busy time inter | CareerCup