Force deduction solution summary 729- my schedule I

Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

Achieve one MyCalendar Class to store your schedule . If the schedule to be added does not cause Repeat Booking , You can store this new schedule .

When there is some time overlap between the two schedules （ For example, both schedules are in the same time ）, It will produce Repeat Booking .

The schedule can use a pair of integers start and end Express , The time here is a half open interval , namely [start, end), The set of real Numbers  x For the range of ,  start <= x < end .

Realization MyCalendar class ：

MyCalendar() Initialize calendar object .
boolean book(int start, int end) If the schedule can be successfully added to the calendar without causing duplicate bookings , return true . otherwise , return false  And don't add the schedule to the calendar .
 

Example ：

Input ：
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output ：
[null, true, false, true]

explain ：
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False , This schedule cannot be added to the calendar , Because of time 15 Has been booked by another schedule .
myCalendar.book(20, 30); // return True , This schedule can be added to the calendar , Because the first schedule is booked at less than each time 20 , And does not include time 20 .
 

Tips ：

0 <= start < end <= 109
Each test case , call book The maximum number of methods is 1000 Time .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/my-calendar-i
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  With two List Loading starts and ends ,list1 Date of storage start ,list2 Date of storage end .
*  Each time a new date start When , All queries are in list1 and start An equal or smaller number s1, Then find the corresponding end date e1.
*  There are four situations 
* start>=e1： Then put start and end Insert into List in ;
* start<e1： disqualification , return false

Code ：

public class Solution729 {

    public static class MyCalendar {
        List<Integer> startList = new ArrayList<>();
        List<Integer> endList = new ArrayList<>();

        public MyCalendar() {

        }

        public boolean book(int start, int end) {
            if (startList.size() == 0) {
                startList.add(start);
                endList.add(end);
                return true;
            }
            int i = middel2Search(startList, start);
            if (i == -1) {
                if (end > startList.get(0)) {
                    return false;
                }
                startList.add(0, start);
                endList.add(0, end);
                return true;
            }
            Integer e1 = endList.get(i);
            Integer s2 = Integer.MAX_VALUE;
            if (i < startList.size() - 1) {
                s2 = startList.get(i + 1);
            }
            if (start >= e1 && end <= s2) {
                startList.add(i + 1, start);
                endList.add(i + 1, end);
                return true;
            }
            return false;
        }

        /**
         *  Two points search , Returns a value equal to or less than 
         *
         * @param node
         */
        public int middel2Search(List<Integer> list, int node) {
            if (list.size() == 0) {
                return 0;
            }
            int start = 0;
            int end = list.size() - 1;
            while (start <= end) {
                int startNode = list.get(start);
                int endNode = list.get(end);
                if (node < startNode) {
                    return start - 1;
                }
                start++;
                if (node >= endNode) {
                    return end;
                }
                end--;
            }
            return start - 1;
        }
    }
}