Q003_Grayon_solution

[Grayon]

Question_ID: Q003

Language: C++

Time Cost: 60+mins

Time Complexity: O(n^2)

Solution

两两检查合并有交点的矩形，放至容器尾部，继续检查。这样就可以直接跳过已检查的矩形。

My Code

#include <iostream>
#include <vector>
using namespace std;
class Rectangle {
public:
    Rectangle(int u,int d,int l,int r);
    bool hasOverlap(Rectangle& aRectangle);
    Rectangle combine(Rectangle& aRectangle);
    void printInfo();
private:
    int u, d, l, r;
};

Rectangle::Rectangle(int u,int d,int l,int r) {
    this->u = u;
    this->d = d;
    this->l = l;
    this->r = r;
}

bool Rectangle::hasOverlap(Rectangle& aRectangle) {
    return u >= aRectangle.d && d <= aRectangle.u && l <= aRectangle.r && r >= aRectangle.l;
}

Rectangle Rectangle::combine(Rectangle& aRectangle) {
    return Rectangle(max(u,aRectangle.u),min(d,aRectangle.d),min(l,aRectangle.l),max(r,aRectangle.r));
}

void Rectangle::printInfo() {
    printf("%d,%d,%d,%d\n",u,d,l,r);
}

vector<Rectangle> merge(vector<Rectangle>& rectangles)
{
    vector<Rectangle> result = vector<Rectangle>(rectangles);
    for (int i = 1; i < result.size(); i++) {
        for (int j = 0; j < i; j++) {
            Rectangle r = result[i];
            if (r.hasOverlap(result[j])) {
                Rectangle combined = r.combine(result[j]);
                result.erase(result.begin() + i);
                result.erase(result.begin() + j);
                result.push_back(combined);
                i -= 2;
                break;
            }
        }
    }
    return result;
}

int main(int argc, const char * argv[]) {
    vector<Rectangle> input, output;
    int u, d, l, r;
    while (scanf("%d,%d,%d,%d",&u,&d,&l,&r)) {
        input.push_back(Rectangle(u,d,l,r));
    }
    output = merge(input);
    for (int i = 0; i < output.size(); ++i) {
        output[i].printInfo();
    }
    return 0;
}

Other

自己写的正向循环是O(n^3)，学习D师的方法，把循环反过来就能直接跳过已检查过的数据。