Find free time from a range of users


  • 0
    S

    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);
    

  • 1

    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();
                    freeIntervals.add(new Pair(peek.y, top.x));
                }
            }
            
            return freeIntervals;
            
        }
        
        public static void main(String[] args) {
            Solution obj = new Solution();
                        
            ArrayList<Pair> userIntervals = new ArrayList<Pair>();
            userIntervals.add(new Pair(1,2));
            userIntervals.add(new Pair(5,6));
            userIntervals.add(new Pair(1,3));
            userIntervals.add(new Pair(4,10));
            
            
            ArrayList<Pair> freeIntervals = obj.findFreeIntervals(userIntervals);
                
            for(Pair p : freeIntervals) {
                System.out.println("(" + p.x + " , "+ p.y + ")");
            }
        }
    }
    
    
    

  • 0
    M

    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

  • 0
    A

    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.


  • 1
    C

    merge interval from leetcode


  • 0
    K

    Maybe something like this...pseudocode.

    int overlapTimes[] = new int[24];
    
    void addIntervalArray(Array<Intervals> intervals) {
        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) {
               resultIntervals.add(new Interval(start, i-1);
               withinInterval = false;
           }
        }
    
        return resultInterval;
    }
    

  • 0

    @ramanpreetSinghKhinda Why use dequeue implements a stack?


  • 0
    A

    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{
    	                result.add(pre);
    	                pre = curr;
    	            }
    	        }
    	        result.add(pre);
    	        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);
    	            freeIntervals.add(gapInterval);
    	            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){
    	    			allIntervals.add(interval);
    	    		}
    	    	}
    	    	
    	    	List<Interval> mergedIntervals = merge(allIntervals);
    	    	List<Interval> freeIntervals = gaps(mergedIntervals);  
    	    	
    	    	return freeIntervals;
    	    }
    

  • 1
    S

    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));
    
    

  • 0
    J

    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.


Log in to reply
 

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