850. Rectangle Area II

이 문 제 는 정말 수준 을 시험 하 는 것 이다.나 는 두 번 째 로 했 는데, 아직 한 시간 이 넘 게 걸 렸 다.나 는 Sweet Line, Interval, TreeSet 세 가지 데이터 구 조 를 이용 하여 이 문 제 를 해결 했다.정말 기본기 에 대한 큰 시련 이다.사고방식 은 스캐닝 라인 이 직사각형 을 좌우 두 줄 로 뜯 어 한 수조 에 던 진 다음 에 x 좌표 에 따라 정렬 한 다음 에 각 x 위치의 선분 을 함께 처리 하 는 것 이다.진행 중인 라인 을 유지 하 는 treeSet 는 x 점 마다 라인 을 추가 하고 라인 을 버 립 니 다.overlap 이 있 는 세 션 을 많이 연 셈 입 니 다. x 시 마다 세 션 을 끄 고 세 션 을 새로 연 셈 입 니 다.x 위치 마다 session 을 업데이트 합 니 다.각 x 위치 에서 이미 시 작 된 것 과 이 x 위치 에서 방금 닫 힌 session 이 얼마나 많은 면적 을 기 여 했 는 지 보 세 요.overlap 이 존재 하기 때문에 merge Interval 의 문제 입 니 다.merge interval 후 커버 할 수 있 는 최대 길이 가 얼마 인지 보 세 요.
내 안에 나 온 bug, TreeSet 과 List Of line 은 두 개의 서로 다른 비교 기 가 있 을 것 이다. 나 는 같은 것 을 사 용 했 고 bug 가 나 왔 다. 사실은 Segment Tree 로 도 할 수 있다.안 쓸 게 요.아래 의 이 해법 은 정말 훌륭 하 다.https://leetcode.com/problems/rectangle-area-ii/discuss/138028/Clean-Recursive-Solution-Java

class Solution {
    public int rectangleArea(int[][] rectangles) {
        List lineList = new ArrayList<>();
        int i = 0;
        for (int[] rect : rectangles) {
            lineList.add(new Line(rect[0], rect, i));
            lineList.add(new Line(rect[2], rect, i++));
        }
        Collections.sort(lineList, new Comparator(){
            public int compare(Line o1, Line o2) {
                return o1.x - o2.x;
            }
        });
        
        
        TreeSet treeSet = new TreeSet<>();
        Integer lastX = null;
        int slow = 0, fast = 0; 
        long ans = 0;
        while (fast < lineList.size()) {
            int curX = lineList.get(fast).x;
            treeSet.add(lineList.get(fast));
            while (fast + 1 < lineList.size() && lineList.get(fast + 1).x == (curX)) {
                treeSet.add(lineList.get(++fast));
            }
            if (lastX == null) {
                lastX = curX;
            } else {
                ans += getArea(treeSet, curX, lastX);
                ans %= 1000000007;
                lastX = curX;
            }
            fast++;
        }
        return (int) ans;
    }
    
    private long getArea(TreeSet treeSet, int x2, int x1) {
        List intervals = new ArrayList<>();
        Iterator it = treeSet.iterator();
        while(it.hasNext()) {
            Line line = it.next();
            if (line.start == x2) continue;
            intervals.add(new Interval(line.low, line.hi));            
            if (line.end == x2) it.remove();
        }
        return (long) (x2 - x1) * ((long) mergeIntervalAndCombine(intervals));
    }
    private int mergeIntervalAndCombine(List list) {
        int ans= 0;
        Interval holder = null;
        for (Interval itv : list) {
            if (holder == null) {
                holder = new Interval(itv.start, itv.end);
                continue;
            }
            if (itv.start > holder.end) {
                ans += holder.end - holder.start;
                holder.start = itv.start;
                holder.end = itv.end;
            } else {
                holder.end = Math.max(holder.end, itv.end);
            }
        }
        if (holder != null) ans += holder.end - holder.start;
        return ans;
    }
}
class Interval {
    int start, end;
    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

class Line implements Comparable {
    int x;
    int low, hi;
    int start, end;
    int id;
    public Line(int x, int[] rec, int id) {
        this.x = x;
        this.low = rec[1];
        this.hi = rec[3];
        this.start = rec[0];
        this.end = rec[2];
        this.id = id;
    }
    @Override 
    public int compareTo(Line that) {
        if (this.low != that.low) return this.low < that.low ? -1 : 1;       
        return this.id - that.id; 
//     id  ，treeSet  compare 0   entry    ！！
    }
}