Q003_ryanorz_solution

[ryanorz]

Question_ID: Q003

Language: c++

Time Cost: 30-mins

Time Complexity: O(n^2)

Solution

和正常人工思路一致，时间复杂度很高，有待优化。想到其他方法再后续补充。

1. 互相之间判断相交
2. 相交，则合并，删除相交的矩形，加入合并的矩形，然后重复1
3. 没有相交的时候返回

My Code

#include <vector>
#include <iostream>

using namespace std;

struct Rect {
    int u; // ymax
    int d; // ymin
    int l; // xmin
    int r; // xmax
};

void printRect(Rect rect) {
    printf("[%d, %d, %d, %d]\n", rect.u, rect.d, rect.l, rect.r);
}

void printRectangles(const vector<Rect>& rects) {
    printf("[\n");
    for (auto rect : rects) {
        printf("\t[%d, %d, %d, %d]\n", rect.u, rect.d, rect.l, rect.r);
    }
    printf("]\n");
}

bool rectIntersection(Rect rec1, Rect rec2) {
    // make rec1 below rec2
    if (rec2.d < rec1.d) swap(rec1, rec2);
    return (rec1.u >= rec2.d) && (rec1.r >= rec2.l) && (rec1.l <= rec2.r);
}

Rect rectMerge(Rect rec1, Rect rec2) {
    return {
        max(rec1.u, rec2.u),
        min(rec1.d, rec2.d),
        min(rec1.l, rec2.l),
        max(rec1.r, rec2.r)
    };
}

void maximumRectangles(vector<Rect>& input) {
    int size = input.size();
    for (int i = 0; i < size; i++) {
        for (int j = i+1; j < size; j++) {
            if (rectIntersection(input[i], input[j])) {
                Rect newRec = rectMerge(input[i], input[j]);
                input.erase(input.begin() + j);
                input.erase(input.begin() + i);
                input.push_back(newRec);
                return maximumRectangles(input);
            }
        }
    }
}

int main() {
    vector<Rect> input = {
        {1, 0, 0, 1},
        {1, 0, 4, 5},
        {3, 2, 2, 5},
        {2, 1, 5, 6}
    };
    printf("Input:\n");
    printRectangles(input);

    printf("output:\n");
    maximumRectangles(input);
    printRectangles(input);
}

Other

[ryanorz]

我发现我的代码是O(n^2)的呀。。。。但判断相交那里的逻辑可以简化一下

bool rectIntersection(const Rectangle& rec1, const Rectangle& rec2) {
    // 其实就是 大中小 要大于 小中大
    return (min(rec1.u, rec2.u) >= max(rec1.d, rec2.d)) &&
    (min(rec1.r, rec2.r) >= max(rec1.l, rec2.l));
}