Java solution beats 97% using sorting process


  • 0
    H
    public class Solution {
    	public boolean isRectangleCover(int[][] rectangles) {
            if (rectangles.length == 0) return true;
              
            Rectangle[] objects = new Rectangle[rectangles.length];
            for (int i = 0; i < rectangles.length; i++)
            	if (!empty(rectangles[i])) objects[i] = new Rectangle(rectangles[i]);
            Arrays.sort(objects);	//sort rectangles in ascending order by rectangle[0] and rectangle[1]
            
            Map<Integer, List<Interval>> map = new HashMap<>();
            int right = initMap(map, objects);
            
            int xl   = objects[0].rectangle[0];
            int down = objects[0].rectangle[1];
            int up 	 = objects[0].rectangle[3];
            
            int index = 0;
            while (index < objects.length && xl == objects[index].rectangle[0]) 
            	up = objects[index++].rectangle[3];
            map.get(xl).add(new Interval(down, up));
            
            List<Interval> list = map.get(xl);
            Interval interval = list.get(0);
            int loc = 1;
            for (int i = 0; i < objects.length; i++) {
            	if (objects[i].rectangle[0] != xl) {
            		if (loc != list.size() || interval != null) return false;
            		
            		xl = objects[i].rectangle[0];
            		list = map.get(xl);
            		if (list.size() == 0) return false;
            		Collections.sort(list);
            		interval = new Interval();
            		loc = setInterval(0, interval, list);
            		i--;
            	} else {
            		if (interval == null) return false;
            		if (interval.from == objects[i].rectangle[1] && interval.to >= objects[i].rectangle[3]) {
            			interval.from = objects[i].rectangle[3];
            			if (!map.containsKey(objects[i].rectangle[2])) return false;
            			map.get(objects[i].rectangle[2]).add(new Interval(objects[i].rectangle[1], objects[i].rectangle[3]));
            			
            			if (interval.from == interval.to) {
            				if (loc == list.size()) interval = null;
            				else loc = setInterval(loc, interval, list);
            			}
            		} else return false;
            	}
            }
            
            list = map.get(right);
            Collections.sort(list);
            int from = down, to = up;
    		for (Interval it : list) {
    			if (it.from == from && to >= it.to) from = it.to;
    			else return false;
    		}
    		return from == to;
    
    	}
        
    	int initMap(Map<Integer, List<Interval>> map, Rectangle[] objects) {
    		int right = 0, xl = objects[0].rectangle[0];
            map.put(xl, new ArrayList<Interval>());
            for (int i = 0; i < objects.length; i++) {
            	if (objects[i].rectangle[0] != xl) {
            		xl = objects[i].rectangle[0];
            		map.put(xl, new ArrayList<Interval>());
            	}
            	if (right < objects[i].rectangle[2]) right = objects[i].rectangle[2];
            }
            map.put(right, new ArrayList<Interval>());
            
            return right;
    	}
    	
    	int setInterval(int loc, Interval interval, List<Interval> list) {
    		int from = list.get(loc).from, to = list.get(loc).to;
    		loc++;
    		while (loc < list.size() && list.get(loc).from == to) to = list.get(loc++).to;
    		interval.from = from;
    		interval.to = to;
    		return loc;
    	}
    	
    	boolean empty(int[] rectangle) {
    		if (rectangle[0] == rectangle[2] || rectangle[1] == rectangle[3]) return true;
    		return false;
    	}
    	
        class Rectangle implements Comparable<Rectangle>{
            int[] rectangle;
            public Rectangle(int[] data) {
            	rectangle = data;
            }
    		
            @Override
    		public int compareTo(Rectangle o) {
    			if (this.rectangle[0] != o.rectangle[0]) 
    				return this.rectangle[0] - o.rectangle[0];
    			return this.rectangle[1] - o.rectangle[1];
    		}
        }
        
        class Interval implements Comparable<Interval>{
        	int from;
        	int to;
        	public Interval() {}
        	
        	public Interval(int from, int to) {
        		this.from = from;
        		this.to = to;
        	}
    
    		@Override
    		public int compareTo(Interval o) {
    			return this.from - o.from;
    		}
        }
    	
    }
    

Log in to reply
 

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