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

• 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++){
}
}
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;
}
}
``````

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