# Find free time from a range of users

• Given a list of intervals for many users, i.e:

A = [(1,2), (5,6)]
B = [(1,3)]
C = [(4,10)]

Return the list of free intervals from all three, in this case would be: [(3,4)]

more formally the signature would be:

``````vector<Interval> get_free_time(vector<vector<Interval>>& users_availability);
``````

• Java Solution

``````import java.io.*;
import java.util.*;

class Pair {
int x, y;

public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}

class Solution {

private ArrayList<Pair> findFreeIntervals(ArrayList<Pair> intervalList) {
ArrayList<Pair> freeIntervals = new ArrayList<>();

if(null == intervalList) {
return freeIntervals;
}

int count = intervalList.size();
if(count <= 1) {
return freeIntervals;
}

// Sort the intervalList
Collections.sort(intervalList, new Comparator<Pair>() {
@Override
public int compare(Pair p1, Pair p2) {
if(p1.x > p2.x) {
return 1;
}

if(p1.x < p2.x) {
return -1;
}

if(p1.x == p2.x) {
if(p1.y > p2.y) {
return 1;
}

if(p1.y < p2.y) {
return -1;
}

if(p1.y == p2.y) {
return 0;
}
}

return 0;
}
});

// Merge all the intervals using Stacks
Deque<Pair> stack = new ArrayDeque<Pair>();
stack.push(intervalList.get(0));

Pair top = null;
Pair peek = null;

for(Pair p : intervalList) {
peek = stack.peek();

if(peek.y >= p.x) {
int yCord = peek.y > p.y ? peek.y : p.y;

top = new Pair(peek.x, yCord);

stack.pop();
stack.push(top);
} else {
stack.push(p);
}
}

while(null != stack && stack.size() > 0) {
top = stack.pop();

if(null != stack && stack.size() > 0) {
peek = stack.peek();
}
}

return freeIntervals;

}

public static void main(String[] args) {
Solution obj = new Solution();

ArrayList<Pair> userIntervals = new ArrayList<Pair>();

ArrayList<Pair> freeIntervals = obj.findFreeIntervals(userIntervals);

for(Pair p : freeIntervals) {
System.out.println("(" + p.x + " , "+ p.y + ")");
}
}
}

``````

• Here's a pseudocode in python that might work for this problem

``````def isIntersecting(item1,item2):
if(max(item1[0],item2[0])>=min(item1[1],item2[1])):
return 1
return None

def merge(item1,item2):
return [min(item1[0],item2[0]),max(item1[1],item2[1])]

def solve(lists):
#flatten the list of the lists
mergedlist=[item for sublist in lists for item in sublist]

#sort the list on the basis of the starting time
sorted(mergedlist,key=lambda x:x[0])

#make a stack to find the merging intervals
stack=[]

#stack that holds the non intersecting intervals
res=[]

stack.append(mergedlist[0])
n=len(mergedlist)

for i in range(1,n):
temp=mergedlist[i]
#keep merging the intersecting intervals
while(isIntersecting(stack[-1],temp):
temp=merge(stack[-1],mergedlist)
stack.pop()
stack.append(temp)
#if the stack has more than one intervals
#join the last 2 free intervals
if(len(stack)>1):
res.append([max(stack[-1]),min(stack[-2])])

return res``````

• put all the intervals in min heap based on start time. Merge them.
keep the merged intervals in an array. Traverse the array from 1 to n. A variable prev can hold array[0]. Free intervals will be prev end time and current start time.

• merge interval from leetcode

• Maybe something like this...pseudocode.

``````int overlapTimes[] = new int[24];

for (Interval interval in intervals)
for(int i = interval.start; i <= interval.end; i++)
overlapTimes[i] +=1;
}

Array<Intervals> getFreeTimes(int userCounts) {
Array<Intervals> resultIntervals = new Array<Intervals>();

int start;
bool withinInterval;

for (int i = 0; i.count(); i++) {
if (overlapTimes(i) == userCounts) {
if (!withinInterval) {
start = i
withinInterval = true;
}
} else if (withinInterval) {
withinInterval = false;
}
}

return resultInterval;
}
``````

• @ramanpreetSinghKhinda Why use dequeue implements a stack?

• I solved the problem by first merging all the intervals for the users and then iterating through the resulting intervals and creating new gap intervals.

``````	   static class Interval {
int start;
int end;
public Interval() { start = 0; end = 0; }
public Interval(int s, int e) { start = s; end = e; }
}

static class IntervalComparator implements Comparator<Interval> {
public int compare(Interval i1, Interval i2){
return i1.start - i2.start;
}
}

static List<Interval> merge(List<Interval> intervals) {
List<Interval> result = new ArrayList<Interval>();
Collections.sort(intervals, new IntervalComparator());
Interval pre = intervals.get(0);
for(int i=1;i<intervals.size();i++){
Interval curr = intervals.get(i);
if(pre.end >= curr.start){
Interval newInterval = new Interval(Math.min(pre.start, curr.start), Math.max(pre.end, curr.end));
pre = newInterval;
}else{
pre = curr;
}
}
return result;
}

static List<Interval> gaps(List<Interval> intervals) {
List<Interval> freeIntervals = new ArrayList<>();
if(intervals.size() == 0) return freeIntervals;

Interval pre = intervals.get(0);

for(int i=1;i<intervals.size();i++){
Interval curr = intervals.get(i);
Interval gapInterval = new Interval(pre.end, curr.start);
pre = curr;
}

return freeIntervals;
}

static List<Interval> findFreeTime(List<List<Interval>> userAvailability){
List<Interval> allIntervals = new ArrayList<>();

for(List<Interval> inList : userAvailability){
for(Interval interval : inList){
}
}

List<Interval> mergedIntervals = merge(allIntervals);
List<Interval> freeIntervals = gaps(mergedIntervals);

return freeIntervals;
}
``````

• JS version:

``````function findAvailableTime(intervals) {
let startArr = [];
let endArr = [];
let result = [];
for (let person of intervals) {
for (let interval of person) {
startArr.push(interval[0]);
endArr.push(interval[1]);
}
}
startArr.sort((a,b)=>a-b);
endArr.sort((a,b)=>a-b);
let start = startArr[0];
let end = endArr[0];
for (let i = 1; i < startArr.length; i++) {
if (startArr[i] <= end) {
end = Math.max(end, endArr[i]);
} else {
start = startArr[i];
result.push([end, start]);
end = endArr[i];
}
}
return result;
}

let timeArr = [
[[1, 3], [6, 7]],
[[2, 4]],
[[2, 3], [9, 12]]
];
console.log('Finding Available time slots: ' + findAvailableTime(timeArr));

``````

• Instantly, you can think of an O(N) solution.

When given intervals, for example (a,b) and (c,d) where d > b > c, we know that there will be no free interval between a and d. If all the intervals are sorted by its start time, we could just iterate through the array of intervals to find all (s,e) such that there are (x,s) and (e,y) such that s <= e.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.