C# Solution using Binary Search Insert Position (with explanatory comments)


  • 0
    K
    public class MyCalendar {
        
        public struct interval{
            public int start;
            public int end;
            public interval(int s, int e){
                start = s;
                end = e;
            }
        }
        List<interval> real;
    
        public MyCalendar() {
            real = new List<interval>();       
        }
        
        public int BinSearchInsertPos(List<interval> list, int t) {        
            int first = 0;
            int last = list.Count - 1;
            while (first <= last) {
                int mid = (first+last)/2;
                if (list[mid].start == t) 
                    return -1;
                else if (list[mid].start < t)
                    first = mid+1;
                else
                    last = mid -1 ;
            }
            return first;
        }    
        
        // First we find an insert position using binary search according to the start point of the interval
        // Then we compare the end point of the previous one (if exists) with the start point of the new one and
        // we compare the end point of the new one with the start point of the next one (if exists)
        // If it is suitable we insert it to the list and return true, otherwise we return false
        // After each call of the funciton the list stays sorted according to the start points of the intervals
        public bool Book(int start, int end) {            
            interval newrec = new interval(start, end - 1);
            int insert = 0;
            if (real.Count > 0){                
                insert = BinSearchInsertPos(real, start);
                if (insert == -1) //if start point exists we cannot insert it to the list
                    return false;
                if (insert <= real.Count - 1 && newrec.end >= real[insert].start)
                    return false;         
                if (insert >= 1 && real[insert - 1].end >= newrec.start)
                    return false;
            }            
            real.Insert(insert, newrec);        
            return true;
        }
    }
    
    

Log in to reply
 

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