A java sweep line solution, could be generalized to solve k rectangles union problem


  • 1
    J

    Though this solution seems to be an overkill to this problem, it could be generalized to solve k rectangles union area problem. Just need to initialize 'events' properly.
    an useful reference:
    https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/

    public class Solution {
        class Pair{
            int x;
            int y;
            public Pair(int x, int y){
                this.x = x;
                this.y = y;
            }
            
            public boolean equals(Object o){
                if(o instanceof Pair){
                    Pair p = (Pair) o;
                    return this.x == p.x && this.y == p.y; 
                } 
                return false;
            }
            
            public int hashCode(){
                return new Integer(x).hashCode() +new Integer(y).hashCode();
            }
        }
    
        public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
            List<int[]> events = new ArrayList<>(4);
            events.add(new int[]{A, A, B, C, D});
            events.add(new int[]{C, A, B, C, D});
            events.add(new int[]{E, E, F, G, H});
            events.add(new int[]{G, E, F, G, H});
            Collections.sort(events, new Comparator<int[]>(){
                public int compare(int[] i1, int[] i2){
                    if(i1[0] == i2[0]){
                        return i1[1]-i2[1];
                    }
                    return i1[0]-i2[0];
                }
            });
            int area = 0, prev = events.get(0)[0], index = 0;
            Map<Pair, Integer> map = new HashMap<Pair, Integer>();
            while(index < events.size()){
                int time = events.get(index)[0];
                area = area + (time-prev)*computeLength(map);
                prev = time;
                while(index < events.size() && events.get(index)[0] == time){
                    Pair interval = new Pair(events.get(index)[2], events.get(index)[4]);
                    if(events.get(index)[0] == events.get(index)[1]){
                        map.put(interval, map.getOrDefault(interval, 0)+1);
                    } else if(events.get(index)[0] == events.get(index)[3]){
                        if(map.get(interval) == 1){
                            map.remove(interval);    
                        }else{
                            map.put(interval, map.get(interval)-1);
                        }
                    }
                    index++;
                }
            }
            return area;
        }
        
        private int computeLength(Map<Pair, Integer> map){
            if(map.isEmpty()) return 0;
            List<int[]> intervals = new ArrayList<>();
            for(Pair entry : map.keySet()){
                for(int i=0; i<map.get(entry); i++){
                    intervals.add(new int[]{entry.x, entry.y});
                }
            }
            Collections.sort(intervals, new Comparator<int[]>(){
                public int compare(int[] i1, int[] i2){
                    if(i1[0] == i2[0]){
                        return i1[1]-i2[1];
                    }
                    return i1[0]-i2[0];
                }
            });
            int length = intervals.get(0)[1] - intervals.get(0)[0], prev = intervals.get(0)[1];
            for(int i=1; i<intervals.size(); i++){
                if(intervals.get(i)[0] <= prev){
                    if(intervals.get(i)[1] > prev){
                        length = length + intervals.get(i)[1]-prev;
                        prev = intervals.get(i)[1];
                    }
                }else{
                    length = length + intervals.get(i)[1] - intervals.get(i)[0];
                    prev = intervals.get(i)[1];
                }
            }
            return length;
        }
    }
    

Log in to reply
 

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