[Java/C++] Clean Code with Explanation


  • 23

    The big idea is pretty simple:
    Each time of book, instead of fail a book when there is 1 or more overlap with existing books as in MyCalendar I, we just want to make sure these overlaps does not overlap - having overlap is now ok, but overlapped period cannot be overlapped again.
    So we just need to keep track of all the overlaps with any previous books

    MyCalendar I can be reused to track the overlaps during each book.

    How to calculate overlap of 2 intervals
    Assume a start earlier than b, (if not reverse), there could be 3 case, but in any case, an overlap(either positive or negative) can always be represented as:
    (max(a0, b0), min(a1, b1))

    case 1: b ends before a ends:
    a: a0 |-------------| a1
    b:     b0 |-----| b1
    
    case 2: b ends after a ends:
    a: a0 |--------| a1
    b:     b0 |--------| b1
    
    case 3: b starts after a ends: (negative overlap)
    a: a0 |----| a1
    b:              b0 |----| b1
    

    Java

    class MyCalendarTwo {
        private List<int[]> books = new ArrayList<>();    
        public boolean book(int s, int e) {
            MyCalendar overlaps = new MyCalendar();
            for (int[] b : books)
                if (Math.max(b[0], s) < Math.min(b[1], e)) // overlap exist
                    if (!overlaps.book(Math.max(b[0], s), Math.min(b[1], e))) return false; // overlaps overlapped
            books.add(new int[]{ s, e });
            return true;
        }
    
        private static class MyCalendar {
            List<int[]> books = new ArrayList<>();
            public boolean book(int start, int end) {
                for (int[] b : books)
                    if (Math.max(b[0], start) < Math.min(b[1], end)) return false;
                books.add(new int[]{ start, end });
                return true;
            }
        }
    }
    

    C++

    class MyCalendar {
        vector<pair<int, int>> books;
    public:
        bool book(int start, int end) {
            for (pair<int, int> p : books)
                if (max(p.first, start) < min(end, p.second)) return false;
            books.push_back({start, end});
            return true;
        }
    };
    
    class MyCalendarTwo {
        vector<pair<int, int>> books;
    public:
        bool book(int start, int end) {
            MyCalendar overlaps;
            for (pair<int, int> p : books) {
                if (max(p.first, start) < min(end, p.second)) { // overlap exist
                    pair<int, int> overlapped = getOverlap(p.first, p.second, start, end);
                    if (!overlaps.book(overlapped.first, overlapped.second)) return false; // overlaps overlapped
                }
            }
            books.push_back({ start, end });
            return true;
        }
    
        pair<int, int> getOverlap(int s0, int e0, int s1, int e1) {
            return { max(s0, s1), min(e0, e1)};
        }
    };
    

    Another way to calculate overlap of 2 intervals
    a started with b, or, b started within a:

    a:                     |---------|
    b:
    a0<b0 & a1<b0:  |----|
    a0<b0 & a1>b0:  |------------| (a started within b)
    a0<b0 & a1>b1:  |-------------------| (a started within b)
    a0>b0 & a0<b1:            |----|  (b started within a)
    a0>b0 & a0>b1:            |---------| (b started within a)
    a0>b1 & a1>b1:                      |----|
    
    

  • 0
    H

    You code is clean but I can not fully understand. Like, each time to call book function in MyCalendarTwo, you create a new instance of Mycalendar. So what are stored in MyCalendar's books, and MyCalendarTwo's books. Can you explain it with one small example in detail?


  • 1
    H

    @hliuxjtu-163.com Oh, I see, every time you first find an overlap, then check if this overlap is valid, whether it's valid or not, you put this overlap into another variable as useful information. Until next time you find an overlap that overlaps with the any existed overlap. Clever!


  • 0
    A

    Why is MyCalendarTwo marked as easy and MyCalendar as medium? I think it needs to be the exact opposite.


  • 0
    S

    @alexander Would you please explain the time complexity as well as the space complexity?


  • 0

    @sschangi The time complexity is O(N), where N is the number of existing books.


  • 1
    E

  • 0

    class MyCalendarTwo {
    class TreeNode{
    TreeNode left;
    TreeNode right;
    int start;
    int end;
    int count;
    TreeNode(int start, int end) {
    this.start = start;
    this.end = end;
    this.count = 1;
    }
    }

    TreeNode root;
    public MyCalendarTwo() {
        root = new TreeNode(0, 0);
    }
    
    public boolean book(int start, int end) {
        return helper(start, end, root);   
    }
    
    private boolean helper(int start, int end, TreeNode root) {
        TreeNode node = new TreeNode(start, end);
        TreeNode cur = root;
        
        while (cur != null) {
            if (node.end <= cur.start) {
                if (cur.left == null) {
                    cur.left = node;
                    return true;
                }
                cur = cur.left;
            } else if (node.start >= cur.end) {
                if (cur.right == null) {
                    cur.right = node;
                    return true;
                }
                cur = cur.right;
            } else {
                if (cur.count >= 2) {
                    return false;
                }
                int leftstart = Math.min(cur.start, node.start);
                int leftend = Math.max(cur.start, node.start);
                int rightstart = Math.min(cur.end, node.end);
                int rightend = Math.max(cur.end, node.end);
                cur.start = Math.max(cur.start, node.start);
                cur.end = Math.min(cur.end, node.end);
                cur.count++;
                return helper(leftstart, leftend, cur) && helper(rightstart, rightend, cur);
            }
        }
        return false;
    }
    

    }

    I think this could be done in nlog(n) time, but i do not know, there is an error in this code, could someone help me to resolve it?


  • 0
    A

    Why is the time complexity is O(N)? It seems the worst case is O(N^2) since you have two nested for loops (counting the one inside MyCalendar.


Log in to reply
 

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