Q003_让奶牛飞_solution

[atomiCat]

Question_ID: Q003

Language: JAVA

Time Cost: 120-mins

Time Complexity: 菜鸡算不出来感觉应该是O(n^2)求大佬帮忙分析啊

Solution

1. 按照底边从小到大排序，并用链表包装起来，选取链表第一个矩形作为【当前矩形】 2.从【当前矩形】开始顺着链表依次与【当前矩形】比较，一直比到某个矩形底边比【当前矩形】的顶高 3.若本轮循环有矩形被合并，则从链表中删掉，本次循环结束后，重复2 4.若本轮循环没有矩形被合并，选取下一个矩形作为【当前矩形】，重复2

My Code

public class Main {
    static int[][] input = {
            {1, 0, 0, 1},
            {1, 0, 4, 5},
            {3, 2, 2, 5},
            {2, 1, 5, 6}
    };

    public static void main(String[] a) {
        Rectangle[] r = new Rectangle[input.length];
        for (int i = 0; i < input.length; i++)
            r[i] = new Rectangle(input[i]);
        //按照底边从小到大排序
        Arrays.sort(r, Comparator.comparingInt(rect -> rect.d));
        for (int i = 1; i < r.length; i++)
            r[i - 1].append(r[i]);

        Rectangle that = r[0], next = that.next;
        boolean merged = false;//记录本轮循环有没有矩形被合并
        while (that != null) {
            if (next == null || that.u < next.d) {
                if (merged) merged = false;
                else that = that.next;
                if (that != null) next = that.next;
            } else {
                if (!((next.l < that.l && next.r < that.l) || (next.r > that.r && next.l > that.r))) {
                    that.merge(next);
                    next.remove();
                    merged = true;
                }
                next = next.next;
            }
        }
        that = r[0];
        do {
            System.out.print(that + ",\n");
        } while ((that = that.next) != null);
    }
}

class Rectangle {
    int u, d, l, r;
    Rectangle prev, next;

    public Rectangle(int[] a) {
        u = a[0];
        d = a[1];
        l = a[2];
        r = a[3];
    }

    public void merge(Rectangle rect) {
        u = Math.max(u, rect.u);
        l = Math.min(l, rect.l);
        r = Math.max(r, rect.r);
    }

    public void append(Rectangle r) {
        this.next = r;
        if (r != null)
            r.prev = this;
    }

    public void remove() {
        this.prev.append(this.next);
    }

    @Override
    public String toString() {
        return "[" + u + "," + d + "," + l + "," + r + ']';
    }
}

Other