Intervue featured on Shark TankIntervue featured on Shark Tank - mobile banner

Employee Free Time

Given a list of intervals representing the busy time of 'N' employees, find out if there is a possibility of free time when there are no meetings.

Constraints:

  • 1 <= N <= 10
  • 1 <= intervals.length <= 100
  • intervals[i].length == 2

Examples:

Input: [[[1,3],[6,7]],[[2,4]],[[8,9]]]

Output: [[3,6]]

Explanation: The free time is between 3 to 6.

Solutions

Merging Intervals

Time: O(N log N)Space: O(N)

The solution involves merging all intervals and then finding the free time between them.


public int[][] findFreeTime(int[][][] intervals) {
  
  List<int[]> allIntervals = new ArrayList<>();
  
  for (int i = 0;
  i < intervals.length;
  i++) {
    
    for (int j = 0;
    j < intervals[i].length;
    j++) {
      
      allIntervals.add(intervals[i][j]);
      
    }
    
  }
  
  Collections.sort(allIntervals, (a, b) -> a[0] - b[0]);
  
  List<int[]> merged = new ArrayList<>();
  
  merged.add(allIntervals.get(0));
  
  for (int i = 1;
  i < allIntervals.size();
  i++) {
    
    if (merged.get(merged.size() - 1)[1] >= allIntervals.get(i)[0]) {
      
      merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], allIntervals.get(i)[1]);
      
    }
    else {
      
      merged.add(allIntervals.get(i));
      
    }
    
  }
  
  List<int[]> freeTime = new ArrayList<>();
  
  for (int i = 0;
  i < merged.size() - 1;
  i++) {
    
    if (merged.get(i)[1] < merged.get(i + 1)[0]) {
      
      freeTime.add(new int[] {
        merged.get(i)[1], merged.get(i + 1)[0]}
      );
      
    }
    
  }
  
  return freeTime.toArray(new int[freeTime.size()][]);
  
}

Difficulty: Medium

Category: Interval Scheduling

Frequency: High

Company tags:

GoogleAmazonMicrosoft