Employee free time algorithm
I recently came across an interesting algorithmic question that has multiple approaches. In this question, we are given a problem statement and we need to come up with an efficient solution using algorithms. There are multiple approaches to solve this question, and in this explanation, I will try to cover some of them. Additionally, I will discuss their time and space complexity, ways to improve these approaches, and any variants of this question that exist.
We are given a list containing the schedules of multiple people. Each person’s schedule is a list of non-overlapping intervals in sorted order. An interval is specified with the start time and an end time, both being positive integers. Your task is to find the list of intervals representing the free time for all the people. We are not interested in the interval from negative infinity to zero or from the end of the last scheduled interval in the input to positive infinity.
K → Number of employees
N → Number of intervals per employee
Input
The input to the function is a two-dimensional array of integers. The following is an example input:
[
[[2,3],[7,9]], // Employee1 intervals
[[1,4],[6,7]] // Employee2 intervals
]Output
The following is the output of the above input:
[[4,6]]What is Free-Time
According to the question, “free-time” refers to the time period when employees do not have any scheduled meetings.
Solutions
We can solve this using multiple approaches, we will start wit hbasic approach and see how we can imporve it.
First: Merge result to single collection and sort
One approach to solve this problem is to collect all the time intervals from each employee and sort the resulting collection in ascending order based on the start time of each interval. Once the collection is sorted, we can iterate through the elements one by one and check if there is any free time between the current interval and the previous range. The previous range is built using the smallest start time until the current element and the largest end time until the current element.
If there is free time available between the current interval and the previous range, then we can add this free time to the result, update the previous range, and continue processing.
Code
- Merge all intervals into one collection
private static List<Interval> mergeAllIntervals(List<List<Interval>> allEmployeesIntervals) {
final var mergedIntervals = new ArrayList<Interval>();
for (var employeeIntervals : allEmployeesIntervals) {
mergedIntervals.addAll(employeeIntervals);
}
return mergedIntervals;
}2. Sort the merged result ascending based on start of the interval
mergedIntervals.sort(Comparator.comparingInt(interval -> interval.start));3. Once the collection is sorted now we can find free-time by processing each item.
private static List<Interval> findFreeTime(List<Interval> mergedAndSortedIntervals) {
final var result = new LinkedList<Interval>();
var previousRangeInterval = mergedAndSortedIntervals.get(0);
for (var currentInterval : mergedAndSortedIntervals) {
if (isThereAFreeTime(previousRangeInterval, currentInterval)) {
result.add(new Interval(previousRangeInterval.end, currentInterval.start));
}
previousRangeInterval =
new Interval(previousRangeInterval.start, Math.max(previousRangeInterval.end, currentInterval.end));
}
return result;
} /**
* @param previousRangeInterval: Range having "start" which is the smallest start from the all previous intervals
* and "end" which is the largest end from the all previous intervals
* @param currentInterval: Interval needs to be checked is there an overlap.
* @return boolean: "True" If there is a free-time between previousRange and this interval.
*/
private static boolean isThereAFreeTime(Interval previousRangeInterval, Interval currentInterval) {
return previousRangeInterval.end < currentInterval.start;
}The full code looks something like
public class EmployeeFreeTime {
public record Interval(int start, int end) {
public static Interval of(int start, int end) {
return new Interval(start, end);
}
}
public static List<Interval> slowFreeTime(List<List<Interval>> allEmployeesIntervals) {
final var mergedIntervals = mergeAllIntervals(allEmployeesIntervals);
if (mergedIntervals.isEmpty()) {
return Collections.emptyList();
}
mergedIntervals.sort(Comparator.comparingInt(interval -> interval.start));
return findFreeTime(mergedIntervals);
}
private static List<Interval> mergeAllIntervals(List<List<Interval>> allEmployeesIntervals) {
final var mergedIntervals = new ArrayList<Interval>();
for (var employeeIntervals : allEmployeesIntervals) {
mergedIntervals.addAll(employeeIntervals);
}
return mergedIntervals;
}
private static List<Interval> findFreeTime(List<Interval> mergedAndSortedIntervals) {
final var result = new LinkedList<Interval>();
var previousRangeInterval = mergedAndSortedIntervals.get(0);
for (var currentInterval : mergedAndSortedIntervals) {
if (isThereAFreeTime(previousRangeInterval, currentInterval)) {
result.add(new Interval(previousRangeInterval.end, currentInterval.start));
}
previousRangeInterval =
new Interval(previousRangeInterval.start, Math.max(previousRangeInterval.end, currentInterval.end));
}
return result;
}
private static boolean isThereAFreeTime(Interval previousRangeInterval, Interval currentInterval) {
return previousRangeInterval.end < currentInterval.start;
}
}Time complexity and space complexity of this approach
Time complexity
Let’s define some notations for our input items:
K: Number of employees
N: Maximum number of intervals for any given employee
M: K * N
The current implementation first merges all of these items into one list, which takes worst case O(M²) time. The sorting step takes O(M logM) time. Finally, finding free time by iterating through all of these intervals takes O(M) time.
So total time complexity of the solution is O(M²)
Space complexity:
We have used O(M) space to hold the merged intervals. Additionally, the list which holds the result could have worst case O(M) items, as each interval can have free time between them.
So space complexity is O(M) + O(M) = O(M)
Second: Efficient merging and sorting
In the first approach mentioned above, the slowest operation is merging intervals from all employees into a single collection and then sorting it. If we could reduce the time complexity of this step, we could improve the overall time complexity of our algorithm.
Fortunately, there is some information in the question that we can use to reduce the time complexity. Specifically, the problem states that the intervals of individual employees are already sorted. We can use this information to merge all of the employees’ intervals into a single collection (e.g., a LinkedList).
To do this, we can iterate over all employees’ intervals and, at each iteration, add the smallest start time interval from all employees’ intervals. We only need to increment the index of the employee whose interval was added to the sorted result, since all other intervals from that employee have already been added. We continue this process until all the intervals of all employees are moved to the sorted result. This approach should be faster than the previous approach since it does not require sorting a large collection of intervals.
private static List<Interval> mergeSortedIntervals(List<List<Interval>> allEmployeesIntervals) {
final var sortedMergedResult = new LinkedList<Interval>();
final var eachEmployeeCurrentIndex = new HashMap<Integer, Integer>();
while (true) {
final var currentIterationSmallestInterval
= getCurrentIterationSmallestInterval(allEmployeesIntervals, eachEmployeeCurrentIndex);
// processing done
if (currentIterationSmallestInterval.start == Integer.MAX_VALUE) {
break;
}
sortedMergedResult.add(currentIterationSmallestInterval);
}
return sortedMergedResult;
}this while loop repeats for M(NK) times, as we add one interval to the result sorted list at a time.
eachEmployeeCurrentIndex: this lookup is used to hold current processing interval index of each employee.
`getCurrentIterationSmallestInterval` method looks something like
private static Interval getCurrentIterationSmallestInterval(List<List<Interval>> allEmployeesIntervals,
Map<Integer, Integer> eachEmployeeCurrentIndex) {
var currentIterationSmallestInterval = new Interval(Integer.MAX_VALUE, Integer.MAX_VALUE);
var currentIterationSmallestIntervalEmployee = -1;
for (int employeeNumber = 0; employeeNumber < allEmployeesIntervals.size(); employeeNumber++) {
var indexOfThisEmployee = eachEmployeeCurrentIndex.getOrDefault(employeeNumber, 0);
final var employeeIntervals = allEmployeesIntervals.get(employeeNumber);
if (indexOfThisEmployee == employeeIntervals.size()) {
continue;
}
final var currentEmployeeInterval = employeeIntervals.get(indexOfThisEmployee);
if (currentIterationSmallestInterval.start > currentEmployeeInterval.start) {
currentIterationSmallestInterval = currentEmployeeInterval;
currentIterationSmallestIntervalEmployee = employeeNumber;
}
}
incrementSmallestIntervalEmployeeIndex(eachEmployeeCurrentIndex, currentIterationSmallestIntervalEmployee);
return currentIterationSmallestInterval;
}
private static void incrementSmallestIntervalEmployeeIndex(Map<Integer, Integer> eachEmployeeCurrentIndex,
int currentIterationSmallestIntervalEmployee) {
eachEmployeeCurrentIndex.put(
currentIterationSmallestIntervalEmployee,
eachEmployeeCurrentIndex.getOrDefault(currentIterationSmallestIntervalEmployee, 0) + 1
);
}As shown in the above code, this method gets one interval from each employee’s interval list, and the element to get is maintained in the eachEmployeeCurrentIndex lookup.
Time complexity of this method is O(K) where K is number of employees.
So overall time complexity of this merge solution is O(MK) or O(NK²).
O(M) for while loop and in each while loop we perform O(K) to find next smallest interval, so Overall O(MK) or O(NK²).
The whole solution looks as
public class EmployeeFreeTime {
public record Interval(int start, int end) {
public static Interval of(int start, int end) {
return new Interval(start, end);
}
}
public static List<Interval> slowFreeTimeImproved(List<List<Interval>> allEmployeesIntervals) {
final var mergedIntervals = mergeSortedIntervals(allEmployeesIntervals);
if (mergedIntervals.isEmpty()) {
return Collections.emptyList();
}
return findFreeTime(mergedIntervals);
}
private static List<Interval> mergeSortedIntervals(List<List<Interval>> allEmployeesIntervals) {
final var sortedMergedResult = new LinkedList<Interval>();
final var eachEmployeeCurrentIndex = new HashMap<Integer, Integer>();
while (true) {
final var currentIterationSmallestInterval
= getCurrentIterationSmallestInterval(allEmployeesIntervals, eachEmployeeCurrentIndex);
// processing done
if (currentIterationSmallestInterval.start == Integer.MAX_VALUE) {
break;
}
sortedMergedResult.add(currentIterationSmallestInterval);
}
return sortedMergedResult;
}
private static Interval getCurrentIterationSmallestInterval(List<List<Interval>> allEmployeesIntervals,
Map<Integer, Integer> eachEmployeeCurrentIndex) {
var currentIterationSmallestInterval = new Interval(Integer.MAX_VALUE, Integer.MAX_VALUE);
var currentIterationSmallestIntervalEmployee = -1;
for (int employeeNumber = 0; employeeNumber < allEmployeesIntervals.size(); employeeNumber++) {
var indexOfThisEmployee = eachEmployeeCurrentIndex.getOrDefault(employeeNumber, 0);
final var employeeIntervals = allEmployeesIntervals.get(employeeNumber);
if (indexOfThisEmployee == employeeIntervals.size()) {
continue;
}
final var currentEmployeeInterval = employeeIntervals.get(indexOfThisEmployee);
if (currentIterationSmallestInterval.start > currentEmployeeInterval.start) {
currentIterationSmallestInterval = currentEmployeeInterval;
currentIterationSmallestIntervalEmployee = employeeNumber;
}
}
incrementSmallestIntervalEmployeeIndex(eachEmployeeCurrentIndex, currentIterationSmallestIntervalEmployee);
return currentIterationSmallestInterval;
}
private static void incrementSmallestIntervalEmployeeIndex(Map<Integer, Integer> eachEmployeeCurrentIndex,
int currentIterationSmallestIntervalEmployee) {
eachEmployeeCurrentIndex.put(
currentIterationSmallestIntervalEmployee,
eachEmployeeCurrentIndex.getOrDefault(currentIterationSmallestIntervalEmployee, 0) + 1
);
}
private static List<Interval> findFreeTime(List<Interval> mergedAndSortedIntervals) {
final var result = new LinkedList<Interval>();
var previousRangeInterval = mergedAndSortedIntervals.get(0);
for (var currentInterval : mergedAndSortedIntervals) {
if (isThereAFreeTime(previousRangeInterval, currentInterval)) {
result.add(new Interval(previousRangeInterval.end, currentInterval.start));
}
previousRangeInterval =
new Interval(previousRangeInterval.start, Math.max(previousRangeInterval.end, currentInterval.end));
}
return result;
}
}Time complexity and space complexity of this approach
Time complexity
Let’s define some notations for our input items:
K: Number of employees
N: Maximum number of intervals for any given employee
M: K * N
The current implementation first merges all of these items into one list, which takes worst case O(MK) time and finding free time by iterating through all of these intervals takes O(M) time.
So total time complexity of the solution is O(MK)
Space complexity:
We have used O(M) space to hold the merged intervals. Additionally, the list which holds the result could have worst case O(M) items, as each interval can have free time between them.
So space complexity is O(M) + O(M) = O(M)
This improvement reduced the time complexity from O((NK)²) to O(NK²).
Third: Using Heap
As we can see in the above solution, the biggest time complexity step is still merging the intervals of K-sorted employees into a single sorted interval. We cannot reduce the time complexity to below O(NK) since we have to check each interval for each employee to collect their intervals into a single sorted interval.
However, we can reduce the time complexity from O(MK) to O(M log K).
In the previous solution, we find the smallestInterval by going over each employee and checking the interval at an index. This process takes O(K) for every iteration when we try to find the smallestInterval.
But if we observe closely, we can see that when we find the smallestInterval for the first time, we use the 0-index interval of each employee. However, when we try to find the second smallest, we use the 0-index interval from the k-1 employees and the 1st index of the previously used employee. Therefore, we are checking the k-1 employees interval again unnecessarily.
How can we avoid it?
We can follow below steps.
- We can find first smallestInterval using the 0-index interval from each employee of k-employees.
- Let’s say smallestInterval is from employee-0 and is added to the sorted result, but remaining (k-1)-employees, result we need to hold it in collection.
- Now we have k-1 employees smallest intervals in a collection from previous step, now we need to add employee-0 next interval to this collection.
To add next interval from employee-0, we some how need to know previously selected smallestInterval was from employe-0, so we need to hold this information somewhere, also we need to know 0-index interval is used next one to be used in 1-index interval.
So to hold all this information we create new class/record with details shown below, and we store this in collection.
private record IndexAwareInterval(int employeeNumber, int intervalIndex, Interval interval){}4. Once we have all employees interval, we will again find the next smallest.
For holding all employees current interval and finding smallest interval from these intervals we need to use a data structure which will provide the smallest item quickly, because we do not want to search on this collection to find smallest interval for each iteration, so we will use Min-Heap data structure for this.
Using Min-Heap will reduce finding smallest in a given K-intervals to O(1).
But once we remove this smallest interval from top of the heap it will take O(log k) to rebalance the heap, also when we add next interval from this employee to this Heap then also it will take O(log k) time complexity.
The new improved code looks as
private static List<Interval> mergeSortedIntervalsUsingHeap(List<List<Interval>> allEmployeesIntervals) {
final var sortedMergedResult = new LinkedList<Interval>();
final var minIntervalHeap =
new PriorityQueue<IndexAwareInterval>(Comparator.comparingInt(indexAwareInterval -> indexAwareInterval.interval.start));
addFirstIntervalsOfEachEmployeeToHeap(minIntervalHeap, allEmployeesIntervals);
while (!minIntervalHeap.isEmpty()) {
final var currentIterationSmallestInterval = minIntervalHeap.remove();
sortedMergedResult.add(currentIterationSmallestInterval.interval);
final var employeeNumber = currentIterationSmallestInterval.employeeNumber;
final var nextIntervalIndex = currentIterationSmallestInterval.intervalIndex + 1;
final var employeeIntervals = allEmployeesIntervals.get(employeeNumber);
if (nextIntervalIndex < employeeIntervals.size()) {
final var indexAwareInterval = new IndexAwareInterval(employeeNumber, nextIntervalIndex, employeeIntervals.get(nextIntervalIndex));
minIntervalHeap.add(indexAwareInterval);
}
}
return sortedMergedResult;
}
private static void addFirstIntervalsOfEachEmployeeToHeap(Queue<IndexAwareInterval> minIntervalHeap,
List<List<Interval>> allEmployeesIntervals) {
for (int employeeNumber=0; employeeNumber < allEmployeesIntervals.size(); employeeNumber++) {
final var employeeIntervals = allEmployeesIntervals.get(employeeNumber);
if (!employeeIntervals.isEmpty()) {
final var indexAwareInterval = new IndexAwareInterval(employeeNumber, 0, employeeIntervals.get(0));
minIntervalHeap.add(indexAwareInterval);
}
}
}As we can see from the above code now the merge runs until the minIntervalHeap is empty, and in each while loop iteration we find the smallest interval, add it to the sorted result and then we pick next interval from the same employee from which we added current smallest interval to the sorted result.
This process continues until we process all the intervals from all the employees.
So now the time complexity for merge and sort intervals is — the outer while loop continues O(M) times, and in each execution of while loop removes and adds a item to the minIntervalHeap which to remove a item in heap takes O(log k) and also to add a item to the heap will also takes O(log k).
So total time complexity of merge and sort intervals is
O(M) * (O(log K) + O(log K)) ==> O(M) * O(log K) ==> O(M logK)
Below is the full code.
public class EmployeeFreeTime {
public record Interval(int start, int end) {
public static Interval of(int start, int end) {
return new Interval(start, end);
}
}
private record IndexAwareInterval(int employeeNumber, int intervalIndex, Interval interval){}
public static List<Interval> freeTime(List<List<Interval>> allEmployeesIntervals) {
final var mergedIntervals = mergeSortedIntervalsUsingHeap(allEmployeesIntervals);
if (mergedIntervals.isEmpty()) {
return Collections.emptyList();
}
return findFreeTime(mergedIntervals);
}
private static List<Interval> mergeSortedIntervalsUsingHeap(List<List<Interval>> allEmployeesIntervals) {
final var sortedMergedResult = new LinkedList<Interval>();
final var minIntervalHeap =
new PriorityQueue<IndexAwareInterval>(Comparator.comparingInt(indexAwareInterval -> indexAwareInterval.interval.start));
addFirstIntervalsOfEachEmployeeToHeap(minIntervalHeap, allEmployeesIntervals);
while (!minIntervalHeap.isEmpty()) {
final var currentIterationSmallestInterval = minIntervalHeap.remove();
sortedMergedResult.add(currentIterationSmallestInterval.interval);
final var employeeNumber = currentIterationSmallestInterval.employeeNumber;
final var nextIntervalIndex = currentIterationSmallestInterval.intervalIndex + 1;
final var employeeIntervals = allEmployeesIntervals.get(employeeNumber);
if (nextIntervalIndex < employeeIntervals.size()) {
final var indexAwareInterval = new IndexAwareInterval(employeeNumber, nextIntervalIndex, employeeIntervals.get(nextIntervalIndex));
minIntervalHeap.add(indexAwareInterval);
}
}
return sortedMergedResult;
}
private static void addFirstIntervalsOfEachEmployeeToHeap(Queue<IndexAwareInterval> minIntervalHeap,
List<List<Interval>> allEmployeesIntervals) {
for (int employeeNumber=0; employeeNumber < allEmployeesIntervals.size(); employeeNumber++) {
final var employeeIntervals = allEmployeesIntervals.get(employeeNumber);
if (!employeeIntervals.isEmpty()) {
final var indexAwareInterval = new IndexAwareInterval(employeeNumber, 0, employeeIntervals.get(0));
minIntervalHeap.add(indexAwareInterval);
}
}
}
private static List<Interval> findFreeTime(List<Interval> mergedAndSortedIntervals) {
final var result = new LinkedList<Interval>();
var previousRangeInterval = mergedAndSortedIntervals.get(0);
for (var currentInterval : mergedAndSortedIntervals) {
if (isThereAFreeTime(previousRangeInterval, currentInterval)) {
result.add(new Interval(previousRangeInterval.end, currentInterval.start));
}
previousRangeInterval =
new Interval(previousRangeInterval.start, Math.max(previousRangeInterval.end, currentInterval.end));
}
return result;
}
}Time complexity and space complexity of this approach
Time complexity
The merge intervals and sort take O(NK logK) → O(M logK)
Now finding free-time by iterating all these intervals takes O(NK) → O(M)
So total time complexity of the solution is O(NK logK) → O(M logK)
Space complexity
Below are the spaces used in the algorithm.
We have intermediate collection to hold all the intervals in sorted order, and the space complexity of this is O(NK) → O(M).
To hold items in the minHeapInterval we use O(K) space.
And for result we also have a linkedList with worst case O(NK) items
So total space used is O(M) * O(K) + O(NK) = O(MK)
This improvement reduced the time complexity from O(MK) to O(M logK) → O(NK logK).
But this uses extra space as the space used increased from O(M) to O(MK).
I hope these tips have been useful. If I missed anything, please let me know. Better yet, I’d love to see the a better performing solution.