Q003_m75n_solution

[13o4t]

Question_ID: Q003

Language: C++

Time Cost: 20-mins

Time Complexity: O(n)

Solution

1. u, d, l, r 拆分为 [d, u] 和 [l, r] 两个线段合并问题，见 Leetcode 56. Merge Intervals
2. sort 按照 d 和 l 的值升序

My Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Rectangle{
    int u;
    int d;
    int l;
    int r;
    Rectangle() : u(0), d(0), l(0), r(0) {}
    Rectangle(int _u, int _d, int _l, int _r) : u(_u), d(_d), l(_l), r(_r) {}
};

bool cmp(const Rectangle& a, const Rectangle& b)
{
    return a.d < b.d ? : a.d == b.d ? a.l < b.l : false;
}

vector<Rectangle> merge(vector<Rectangle>& rectangles)
{
    if (rectangles.empty()) return vector<Rectangle>{};

    vector<Rectangle> res;
    sort(rectangles.begin(), rectangles.end(), cmp);

    res.push_back(rectangles[0]);
    for (int i = 1; i < rectangles.size(); ++i) {
        if (res.back().u < rectangles[i].d || res.back().r < rectangles[i].l || rectangles[i].r < res.back().l) {
            res.push_back(rectangles[i]);
        } else {
            res.back().u = max(res.back().u, rectangles[i].u);
            res.back().l = min(res.back().l, rectangles[i].l);
            res.back().r = max(res.back().r, rectangles[i].r);
        }
    }

    return res;
}

int main(void)
{
    vector<Rectangle> input, output;
    int u, d, l, r;

    while (cin >> u >> d >> l >> r) {
        Rectangle rec(u, d, l, r);
        input.push_back(rec);
    }

    output = merge(input);

    for (int i = 0; i < output.size(); ++i)
        cout << output[i].u << " "
             << output[i].d << " "
             << output[i].l << " "
             << output[i].r << endl;

    return 0;
}

Other

gcc --std=c++11

[ryanorz]

里面的 sort 就导致了时间复杂度不是 O(n) 吧

[13o4t]

Time Complexity: O(n^2)

My Code

#include <iostream>
#include <vector>
#include <tuple>
#include <list>
#include <algorithm>
using namespace std;

vector<tuple<int, int, int, int>> merge(vector<tuple<int, int, int, int>> rectangles)
{
    list<tuple<int, int, int, int>> res(rectangles.begin(), rectangles.end());
    int u1, d1, l1, r1, u2, d2, l2, r2;

    for (auto it1 = res.begin(); it1 != res.end(); ) {
        bool flag = false;
        for (auto it2 = res.begin(); it2 != it1; ++it2) {
            tie(u1, d1, l1, r1) = *it1;
            tie(u2, d2, l2, r2) = *it2;
            if (min(u1, u2) >= max(d1, d2) && max(l1, l2) <= min(r1, r2)) {
                res.emplace_back(max(u1, u2), min(d1, d2), min(l1, l2), max(r1, r2));
                res.erase(it2);
                it1 = res.erase(it1);
                flag = true;
                break;
            }
        }
        if (!flag) it1++;
    }

    return {res.begin(), res.end()};
}

int main(void)
{
    vector<tuple<int, int, int, int>> input, output;
    int u, d, l, r;

    while (cin >> u >> d >> l >> r) {
        input.emplace_back(u, d, l, r);
    }

    output = merge(input);

    for (int i = 0; i < output.size(); ++i) {
        tie(u, d, l, r) = output[i];
        cout << u << " " << d << " " << l << " " << r << endl;
    }

    return 0;
}

Other

g++ -std=c++11

看了 @palayutm 大的代码收获颇多