729. My schedule I / offer II 106 Bipartite graph

729. My schedule I【 Medium question 】【 A daily topic 】

Ideas ：【TreeMap】

Study TreeMap Use , Two ways .
See code Notes for details .

Code 1：

class MyCalendar {
    

    TreeMap<Integer,Integer> treeMap;

    public MyCalendar() {
    
        treeMap = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
    
        // The first is greater than or equal to  start  The range of 
        Map.Entry<Integer,Integer> ceilingEntry = treeMap.ceilingEntry(start);
        // The first is less than or equal to  start  The range of 
        Map.Entry<Integer,Integer> floorEntry = treeMap.floorEntry(start);
        
        // If  floorEntry  by  null  perhaps  floorEntry  Corresponding value ( Indicates the right end of the interval )  Less than or equal to  start
        //  And   meanwhile  ceilingEntry by  null  perhaps  ceilingEntry  The corresponding key ( Represents the left end point of the interval )  Greater than or equal to  end
        //  Then explain the current schedule range   It can be inserted into treeMap Indicates that in the calendar , And will not result in duplicate bookings 
        if((floorEntry == null || floorEntry.getValue() <= start)
            && (ceilingEntry == null || end <= ceilingEntry.getKey())){
    
                treeMap.put(start,end);
                return true;
        }
        // If the above conditions are not met   Then you can't add daily to your calendar , return false
        return false;
    }
}

/** * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); */

Code 2：

class MyCalendar {
    

    TreeMap<Integer,Integer> map;

    public MyCalendar() {
    
        // initialization TreeMap,map in key Is the left end point of the interval （ contain ）,value Is the right end of the interval （ It doesn't contain ）
        map = new TreeMap<>();
        // stay map Add the big boundary of the whole interval 
        // Leftmost -1
        map.put(-1,-1);
        // On the far right is 1000000001
        map.put(1000000001,1000000001);
    }

    public boolean book(int start, int end) {
    
        // seek map in   To insert the left endpoint of the interval  start  Left and right values , Set as left  and right,left Representation ratio start The left end of the small interval  right Representation ratio start The left end of the large interval 
        Integer left = map.floorKey(start),right = map.ceilingKey(start);
        // If right Less than end  Representation ratio start The ratio of the left end point of the large interval end Small   Now insert [start,end) It will definitely cause interval overlap , return false 
        // If left The value ratio of the right end point of the corresponding interval start Big   It will also cause interval overlap   return false
        if (right < end || map.get(left) > start){
    
            return false;
        }
        // Exclude the above   Intervals do not overlap , Then the schedule is successfully inserted 
        map.put(start,end);
        return true;
    }
}

/** * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); */

---

The finger of the sword Offer II 106. Bipartite graph 【 Medium question 】

Ideas ：【DFS】

It's important to understand the topic , The definition of bipartite graph in the title is ：
Divide all nodes of a graph into two independent subsets A and B, And make one of the two nodes of each edge in the graph come from the set A, One comes from the set B.

Then we can use the concept of coloring to try bisection of undirected graphs , Initially, all nodes in the graph are colorless , Starting from any node , Traverse all the nodes in the graph , If the node is not stained , Then dye it red ,
Then traverse all adjacent points of this node , If the adjacency point is not stained , Dye it green , And search all the adjacency points of this adjacency point , If it is not dyed, it will be dyed red ; If the adjacency point has been dyed , And the color is the same as the current node , Then the dyeing fails , The function returns false.
See the notes for the detailed process . Ideas and codes refer to the official solutions .

Code ：

class Solution {
    
    // Definition color Array , Used to mark the color of each node in the undirected graph 
    static int[] color;
    // Define flag bit valid, Used to indicate whether the current status is valid 
    static boolean valid;
    // Define static variables to mark node colors 
    static final int UNCOLORED = 0;
    static final int RED = 1;
    static final int GREEN = 2;

    public boolean isBipartite(int[][] graph) {
    
        int n = graph.length;
        // initialization valid by true, Indicates that the starting state is valid 
        valid = true;
        // Initialize the color array color
        color = new int[n];
        //color The initial value of the assignment is   colourless  UNCOLORED
        Arrays.fill(color,UNCOLORED);
        // Traverse every valid node in the undirected graph 
        for (int i = 0; i < n && valid; i++) {
    
            // If the current node is not colored , Call dfs The function colors it red 
            if (color[i] == UNCOLORED){
    
                dfs(i,RED,graph);
            }
        }
        // Returns the effective state of the node after the undirected graph traversal 
        return valid;
    }
    public void dfs(int node,int c,int[][] graph){
    
        // Set the current node node Dye to the specified color c
        color[node] = c;
        // Record the target color of the adjacent node of the current node cNei, If c In red , be cNei It's green , If c It's green , be cNei In red 
        int cNei = c == RED ? GREEN : RED;
        // Traverse each adjacent node of the current node neighbor
        for (int neighbor : graph[node]) {
    
            // If the adjacent contact is colorless , Then dye the adjacent contact , That is, the node is red , Then dye the adjacent nodes green , Node is green , Then dye the adjacent dots red 
            if (color[neighbor] == UNCOLORED){
    
                // Dye the adjacent dots as cNei Color 
                dfs(neighbor,cNei,graph);
                // If after dyeing , Find out valid by false, Then the coloring function directly returns , Don't continue to dye the next adjacent point 
                if (!valid){
    
                    return;
                }
            }else if (color[neighbor] != cNei){
    
                // If the color of the adjacent contact has been dyed , And its color is not the color to be dyed ( It is the same color as the current node )
                // It will be valid Marked as false, Indicates dyeing failure . The coloring function returns 
                valid = false;
                return;
            }
        }
    }
}