Sharing my o(nlogn) java solution based on a sweeping line


  • 0
    M

    public class Solution {

    class Event {
        int time;
        boolean start;
        int bottom;
        int top;
        
        public Event(int time, boolean start, int bottom, int top) {
            this.time = time;
            this.start = start;
            this.bottom = bottom;
            this.top = top;
        }
    }
    
    private TreeMap<Integer, List<Event>> createEventsMap(int[][] rectangles) {
        
        TreeMap<Integer, List<Event>> map = new TreeMap<Integer, List<Event>>();
        
        for (int i=0; i<rectangles.length; i++) {
            
            Event left = new Event(rectangles[i][0], true, rectangles[i][1], rectangles[i][3]);
            Event right = new Event(rectangles[i][2], false, rectangles[i][1], rectangles[i][3]);
            
            List<Event> events =  map.get(left.time);
            if (events == null) {
                events = new ArrayList<Event>();
                map.put(left.time, events);
            }
            events.add(left);
    
            events =  map.get(right.time);
            if (events == null) {
                events = new ArrayList<Event>();
                map.put(right.time, events);
            }
            events.add(right);
        }
        
        return map;
    }
    
    private int[] boundries(int[][] rectangles) {
        int left=Integer.MAX_VALUE, right=0, top=0, bottom=Integer.MAX_VALUE;
        
        for (int i=0; i<rectangles.length; i++) {
            if (rectangles[i][0] < left) {
                left = rectangles[i][0];
            }
            
            if (rectangles[i][1] < bottom) {
                bottom = rectangles[i][1];
            }
            
            if (rectangles[i][2] > right) {
                right = rectangles[i][2];
            }
    
            if (rectangles[i][3] > top) {
                top = rectangles[i][3];
            }
        }
        
        int[] ret = new int[4];
        ret[0] = left;
        ret[1] = right;
        ret[2] = bottom;
        ret[3] = top;
        
        return ret;
    }
    
    public boolean isRectangleCover(int[][] rectangles) {
        
        int[] bounds = boundries(rectangles);
    
        TreeMap<Integer, List<Event>> map = createEventsMap(rectangles);
        
        TreeMap<Integer, Event> sweepingLine = new TreeMap<Integer, Event>();
        
        for (Integer t : map.navigableKeySet()) {
            List<Event> events = map.get(t);
                               
            int removingLength = 0, addedLength = 0;
            
            for (Event event : events) {
                if (!event.start) {
                	removingLength += event.top - event.bottom;
                    sweepingLine.remove(event.bottom);
                } 
            }
            
            for (Event event : events) {
            	if (event.start) {
            		
            		if (event.top > bounds[3]) {
            			return false;
            		}
    
            		if (event.bottom < bounds[2]) {
            			return false;
            		}
    
            		if (sweepingLine.get(event.bottom) == null) {
                        sweepingLine.put(event.bottom, event);
                        
                        addedLength += event.top - event.bottom;
                                                
                        Integer nextEventTime = sweepingLine.higherKey(event.bottom);
                        if (nextEventTime != null) {
                            Event nextEvent = sweepingLine.get(nextEventTime);
                            if (event.top > nextEvent.bottom) {
                                return false;
                            } 
                        }
                        
                        Integer preEventTime = sweepingLine.lowerKey(event.bottom);
                        if (preEventTime != null) {
                            Event preEvent = sweepingLine.get(preEventTime);
                            if (event.bottom < preEvent.top) {
                                return false;
                            } 
                        }            
            		} else {
            			return false;
            		}
                }            
            }
            
            if (t == bounds[1]) {
            	if (sweepingLine.isEmpty()) {
            		return true;
            	} else {
            		return false;
            	}
            } else if (t == bounds[0]) {
            	int totalLength = bounds[3] - bounds[2];
            	if (addedLength != totalLength) {
            		return false;
            	}
            } else {
            	if (removingLength != addedLength) {
            		return false;
            	}
            }
            
        }
        
        return true;
    }
    

    }


Log in to reply
 

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