O(n log n) sweep line solution


  • 39
    W

    Standard sweep line solution.
    Basic idea:
    Sort by x-coordinate.
    Insert y-interval into TreeSet, and check if there are intersections.
    Delete y-interval.

    public class Event implements Comparable<Event> {
    	int time;
    	int[] rect;
    
    	public Event(int time, int[] rect) {
    		this.time = time;
    		this.rect = rect;
    	}
    	
    	public int compareTo(Event that) {
    		if (this.time != that.time) return this.time - that.time;
    		else return this.rect[0] - that.rect[0];
    	}
    }
    
    public boolean isRectangleCover(int[][] rectangles) {
    	PriorityQueue<Event> pq = new PriorityQueue<Event> ();
            // border of y-intervals
    	int[] border= {Integer.MAX_VALUE, Integer.MIN_VALUE};
    	for (int[] rect : rectangles) {
    		Event e1 = new Event(rect[0], rect);
    		Event e2 = new Event(rect[2], rect);
    		pq.add(e1);
    		pq.add(e2);
    		if (rect[1] < border[0]) border[0] = rect[1];
    		if (rect[3] > border[1]) border[1] = rect[3];
    	}
    	TreeSet<int[]> set = new TreeSet<int[]> (new Comparator<int[]> () {
    		@Override
                    // if two y-intervals intersects, return 0
    		public int compare (int[] rect1, int[] rect2) {
    			if (rect1[3] <= rect2[1]) return -1;
    			else if (rect2[3] <= rect1[1]) return 1;
    			else return 0;
    		}
    	});
    	int yRange = 0;
    	while (!pq.isEmpty()) {
    		int time = pq.peek().time;
    		while (!pq.isEmpty() && pq.peek().time == time) {
    			Event e = pq.poll();
    			int[] rect = e.rect;
    			if (time == rect[2]) {
    				set.remove(rect);
    				yRange -= rect[3] - rect[1];
    			} else {
    				if (!set.add(rect)) return false;
    				yRange += rect[3] - rect[1];
    			}
    		}
                    // check intervals' range
    		if (!pq.isEmpty() && yRange != border[1] - border[0]) {
                            return false;
    			//if (set.isEmpty()) return false;
    			//if (yRange != border[1] - border[0]) return false;
    		}
    	}
    	return true;
    }
    

  • 3

    Very nice way of detecting and handling interval overlaps... I think few people even know/use that set.add returns something (at least I often see people do if (!set.contains(x)) { set.add(x); foo(); } else { bar(); }).

    The if (set.isEmpty()) return false; seems unnecessary, isn't it?


  • 6

    said in O(n log n) sweep line solution:

    Good idea to solve this problem, I read the code very careful, so I write some to make the code easy to understand the logic.

    this way first to sort x-coordinate in order to handle rectangle from left to right
    when the time is same then sort by the rect[0], why do like this?

    this situation happens in like top-right in 4th and bottom-left in 5th point in the below picture.
    0_1472484105868_upload-06c78900-1de6-41a0-b7da-21c4511b25f9

    Because we want to handle rectangle from left to right and every handle process there is only one rectangle in the vertical range, when handle 5th rectangle 4th rect should be removed, handle 2th rect 1th rect should be removed. So we need sort by rect[0] when time is same.

    After the traversal sequence is set by PriorityQueue, we use the treeSet to judge two rect is intersections or not, and we can see every handle process, the yRange should equal the high of the largest rectangle outside if it is true.


  • 0
    W

    @StefanPochmann You are right! I update the code. :)


  • 0
    W

    @zhangCabbage Thanks for this awesome explanation!


  • 0
    X

    how about the example 2. how does the solution cover that case?


  • 0
    W

    @xbwcoding3 yRange should always be border[1] - border[0] or 0 (at the last position).

    So the following part covers ex 2

                    // check intervals' range
    		if (!pq.isEmpty() && yRange != border[1] - border[0]) {
                            return false;
    			//if (set.isEmpty()) return false;
    			//if (yRange != border[1] - border[0]) return false;
    		}
    

  • 0
    Y

    It's really smart that you use TreeSet and its compare() method to find intersections! I only think of TreeSet when I try to sort something.


  • 0
    Y

    Hi Good solution! I'm just a bit confused about the yRange == border[1] - border[0] part. I mean for each rectangular, you stored (enter_time = rec[0], rec) and (leave_time = rec[2], rec) right? So for each rec, the scan line will enter once and leave one. So when it's leaving (time == rect[2]), you subtract the height of the rec from yRange right? And when entering the it, you add the height to the yRange. In this way, shouldn't the yRange is always 0? I'm sure something's wrong with my understanding. Could you explain it? Thanks


  • 0
    Y

    Oh I just noticed you actually checked yRange each time after checking all the entering and leaving rec. Really smart idea! I learnt a lot. Thanks!


  • 0
    Y
    This post is deleted!

  • 3

    The comparator of the tree set is really awesome to detect intersection!

    I hope my explanation below will help. For example, so basically we have three rects: Rect 1 (1, 1, 3, 3); Rect2 (1, 3, 3, 4); and Rect3 (2, 3, 3, 4). Rect3 intersects with Rect2 obviously.

    So what the tree set does is that, when the sweep line goes to the time 2 (x = 2), the tree set still contains Rect2(1, 3, 3, 4) because the right time event (time=3) has not been polled from the priority queue. which means the shaded area is kind of like a horizontal blocking space (x >= 2, 3 <= y <= 4) whenever the new rect is not on the shaded area's bottom left or top right, there is an intersection.

    And the set.add() will return false when the compare func returns 0.

    alt text


  • 0
    I

    What if we allow overlap for this question? Meaning that example 4 is considered as a legal perfect rectangle, how can we tackle this then?


  • 0
    X

    I cannot see the role of the TreeSet here. Elements are added to and removed from this set, but it is not used for judgement in the proces. The only place is if (!set.add(rect)) return false;, but the purpose here is to detect duplication, which is not essential. Right ?

    PS: Sorry. I am wrong. The set here is used to detect overlap, which is very important.


  • 0

    My Java solution of idea of sweepline:

    public boolean isRectangleCover(int[][] rectangles) {
    
    
        PriorityQueue<Interval> pq = new PriorityQueue<Interval>((a, b) -> {
            if(a.x != b.x) return a.x - b.x;
            else {
                if(a.isStart != b.isStart) return a.isStart ? 1 : -1;
                else return a.y1 - b.y1;
            }
        });
    
    
        int bottomy = Integer.MAX_VALUE; // use to record the max hight of rectangle, all hight must equal to max hight
        int topy = Integer.MIN_VALUE;
        for(int[] rect:rectangles){
            bottomy = Math.min(bottomy,rect[1]);
            topy = Math.max(topy,rect[3]);
            Interval start = new Interval(rect[0],rect[1],rect[3]);
            Interval end = new Interval(rect[2],rect[1],rect[3]);
            start.pair = end;
            start.isStart = true;
            end.pair = start;
            end.isStart = false;
            pq.offer(start);
            pq.offer(end);
        }
    
    
        TreeSet<Interval> set = new TreeSet(); // use to simulate sweepline
        int lengthy = 0;
        while(!pq.isEmpty()){
            int x = pq.peek().x;
            while(!pq.isEmpty() && pq.peek().x == x){ // all invervals who x coordinate is same
                Interval inv = pq.poll();
                if(inv.isStart){
                    if(!set.add(inv)) return false;
                    lengthy += inv.y2 - inv.y1;
                } else {
                    set.remove(inv.pair);
                    lengthy -= inv.y2 - inv.y1;
                }
            }
    
    
            if(!pq.isEmpty() && lengthy != topy - bottomy){
                return false;
            }
        }
    
    
        return true;
    }
    

    class Interval implements Comparable<Interval>{
    int x;
    int y1;
    int y2;
    Interval pair;
    boolean isStart;
    Interval(int x,int y1,int y2){
    this.x = x;
    this.y1 = y1;
    this.y2 = y2;
    }

        public int compareTo(Interval that) {
            if(this.isStart != that.isStart) return this.isStart ? 1 : -1;
            else {
                if(this.y2 <= that.y1) return -1;
                else if(that.y2 <= this.y1) return 1;
                else return 0;
            }
        }
    }

  • 0
    O

    I'm surprised by your excellent solution.

    Here I share my understanding of your implementation.

    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;
        }
    }
    

  • 3
    W

    @wddd Really nice solution! Here is my C++ version.

    class Solution {
    public:
        struct Event {
            int tm; // x-axis position.
            int index; // pointer to the rectangle in the given array.
            bool isStart; // This is the left edge of the rectangle, otherwise, right edge.
            Event(int t, int id, bool isS): tm(t), index(id), isStart(isS) {}
        };
    
        bool isRectangleCover(vector<vector<int>>& rectangles) {
            auto compPQ = [&](Event* e1, Event* e2) {
                if(e1->tm != e2->tm) return e1->tm > e2->tm;
                else return rectangles[e1->index][0] > rectangles[e2->index][0];
            };
            priority_queue<Event*, vector<Event*>, decltype(compPQ)> pq(compPQ);
            int bottom = INT_MAX, roof = INT_MIN; 
            for(int i = 0; i < rectangles.size(); i++) {
                const vector<int>& rec = rectangles[i];
                Event* e1 = new Event(rec[0], i, true);
                Event* e2 = new Event(rec[2], i, false);
                pq.push(e1); pq.push(e2);
                bottom = min(bottom, rec[1]);
                roof = max(roof, rec[3]);
            }
            auto compSet = [&](Event* e1, Event* e2) {
                if(rectangles[e1->index][3] <= rectangles[e2->index][1]) return true;
                else return false;
            };
            set<Event*, decltype(compSet)> mySet(compSet);
            int yRange = 0;
            while(!pq.empty()) {
                int tm = pq.top()->tm;
                while(!pq.empty() && tm == pq.top()->tm) {
                    Event* event = pq.top(); pq.pop();
                    const vector<int>& rec = rectangles[event->index]; 
                    if(event->isStart) {
                        auto rt = mySet.insert(event);
                        if(!rt.second) return false; // overlapping!!!
                        yRange += rec[3] - rec[1];
                    }
                    else {
                        mySet.erase(event);
                        yRange -= rec[3] - rec[1];
                    }
                }
                if(!pq.empty() && yRange != roof - bottom) return false;
            }
            return true;
        }
    };
    

  • 0
    Y
    This post is deleted!

  • 0

    Smart idea, I find such sweep line method can be used to check if given rectangles overlap or not.


  • 0
    J

    The idea of using TreeSet to determine overlaps is so brilliant!
    Here is my Java implementation:

    class Rect implements Comparable<Rect> {
            public int y2, y1, x1, x2;
    
            boolean isEnd;
    
            Rect (int[] rect, boolean end) {
                y2 = rect[3];
                y1 = rect[1];
                x1 = rect[0];
                x2 = rect[2];
                isEnd = end;
            }
            public int compareTo(Rect b) {
                if (this.y2 <= b.y1) {
                    return -1;
                } else if (this.y1 >= b.y2) {
                    return 1;
                } else return 0;
            }
        }
    
    
        public boolean isRectangleCover(int[][] rectangles) {
            int top = Integer.MIN_VALUE;
            int bot = Integer.MAX_VALUE;
    
            Rect[] scans = new Rect[rectangles.length * 2];
    
            for (int i = 0; i < rectangles.length * 2; i += 2) {
               scans[i] = new Rect(rectangles[i / 2], false);
               scans[i + 1] = new Rect(rectangles[i / 2], true);
               top = Math.max(top, scans[i].y2);
               bot = Math.min(bot, scans[i + 1].y1);
            }
    
            Arrays.sort(scans, (Rect a, Rect b) -> {
                int valA = a.isEnd ? a.x2 : a.x1;
                int valB = b.isEnd ? b.x2 : b.x1;
                if (valA == valB) {
                    return a.x1 - b.x1;
                }
                return valA - valB;
            });
    
            TreeSet<Rect> set = new TreeSet<>();
            int pos = scans[0].x1;
            int height = 0;
            for (Rect rect: scans) {
                if (rect.isEnd) {
                    if (rect.x2 != pos && height != top - bot) {
                        return false;
                    }
                    set.remove(rect);
                    pos = rect.x2;
                    height -= rect.y2 - rect.y1;
                } else {
                    if (rect.x1 != pos || !set.add(rect)) return false;
                    pos = rect.x1;
                    height += rect.y2 - rect.y1;
                }
            }
            return true;
        }
    

Log in to reply
 

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