O(NlogN) But You Can Learn A Lot


  • 0
    O

    O(NlogN) But You Can Learn A Lot
    The credit is given to https://discuss.leetcode.com/topic/55944/o-n-log-n-sweep-line-solution

    public class Solution {
        class Rect implements Comparable<Rect> {
            int u, d, l, r;
            
            public Rect(int[] rect) {
                l = rect[0]; d = rect[1]; r = rect[2]; u = rect[3]; 
            }
            
            public int compareTo(Rect that) {
                if (this.u <= that.d)
                    return -1;
                else if (this.d >= that.u)
                    return 1;
                else
                    return 0; //Overlap, VERY IMPORTANT PROPERTY for TreeSet to check overlap
            }
        }
        
        class RectLife implements Comparable<RectLife> {
            int time;
            boolean isEnd;
            Rect rect;
            
            public RectLife(int t, boolean ed, Rect rectt) {
                time = t; isEnd = ed; rect = rectt;
            }
            
            public int compareTo(RectLife that) { //Important to also sort rect.l
                return (this.time != that.time) ? this.time - that.time : this.rect.l - that.rect.l;
            }
        }
        
        public boolean isRectangleCover(int[][] rectangles) {
            PriorityQueue<RectLife> pq = new PriorityQueue();
            TreeSet<Rect> set = new TreeSet();
            int bot = rectangles[0][1], top = rectangles[0][3];
            
            for (int[] rt : rectangles) {
                Rect rect = new Rect(rt);
                bot = Math.min(bot, rect.d);
                top = Math.max(top, rect.u);
                
                pq.offer(new RectLife(rect.l, false, rect));
                pq.offer(new RectLife(rect.r, true, rect));
            }
            
            if (pq.isEmpty())
                return false;
            
            int height = 0;
            while (!pq.isEmpty()) {
                int time = pq.peek().time;
                
                while (!pq.isEmpty() && pq.peek().time == time) {
                    RectLife rl = pq.poll();
                    if (!rl.isEnd) {
                        if (set.add(rl.rect))
                            height += rl.rect.u - rl.rect.d;
                        else
                            //set considers there's already a 'same' component, while we defined:
                            //for Rect, 'same' is overlapping.
                            return false; 
                    } else {
                        set.remove(rl.rect);
                        height -= rl.rect.u - rl.rect.d;
                    }
                }
                
                if (!pq.isEmpty() && height != top - bot)
                    return false;
            }
            
            return true;
        }
    }
    

  • 0
    O

    Basic idea:
    Sort by x-coordinate by PriorityQueue.
    Insert y-interval into TreeSet, and check if there are overlapped rectangles.
    Delete y-interval for ending rectangles from TreeSet.


Log in to reply
 

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