Axis­ Aligned Rectangles (Google 面试题， 2016网易游戏校招笔试)

Describe 
an
 algorithm 
that 
takes 
an 
unsorted 
array 
of 
axis‐aligned 
rectangles 
and
 returns 
any 
pair 
of 
rectangles 
that
 overlaps,
 if 
there
 is 
such
 a 
pair.
 
Axis‐aligned
 means
 that
 all 
the
 rectangle
 sides
 are 
either 
parallel
 or
 perpendicular 
to
 the
 x‐
 and
 y‐axis. 

You
 can
 assume 
that
 each
 rectangle
 object
 has
 two 
variables
in
 it: 
the 
x‐y
 coordinates 
of 
the
 upper‐left 
corner 
and 
the 
bottom‐right 
corner.

Good
 Answer: 
Create
 a 
sorted 
array 
of
 the
 x
 coordinates 
of 
the
 left
 and
 right
 edges 
of
 the 
rectangles. 

Then, 
use 
a
 "scanline" 
to
 move
 from
 left 
to 
right 
through
 the
 rectangles. 

Keep 
a
 binary
 search
 tree 
containing 
the
 y 
coordinates 
of 
the
 top
 and
 bottom
 edges 
of 
the
 rectangles
 that
 overlap 
the 
scanline. 

For 
each
 element
 of 
the
 array,
 check
 whether 
it 
is 
a
 left 
or 
right
 edge.
 
If 
it 
is 
a 
right
 edge, 
remove
 the
 corresponding
 top
 and 
bottom
 edges 
from 
the 
BST.

 If 
it 
is 
a
left 
edge,
 search
 the
 BST
 for 
rectangles
 that
 overlap 
the
 current
 rectangle; 
if 
there
 is 
one,
return 
the
 overlap.

 Then,
 add 
the
y
 coordinates 
of
 the
 top
 and
 bottom
edges
 of 
the 
rectangle
 to 
the 
BST.

 The
 search
 takes 
O(n
log
n) 
time,
 since 
it 
takes 
O(n
log
n) 
time
 to
 sort
 the
 rectangles
 and
 each
 of 
the
 2n 
iteration s
takes 
O(log
n)
 time.

C++ Sample Code (Find all pairs of rectangles that overlap): 

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

struct rect {
    int _x1, _x2, _y1, _y2;
    rect(int x1, int x2, int y1, int y2) :
        _x1(x1), _x2(x2), _y1(y1), _y2(y2) {}
};

struct xedge {
    int _x;
    int _is_left;
    int _i_rect;
    xedge(int x, int is_left, int i_rect) :
        _x(x), _is_left(is_left), _i_rect(i_rect) {}
};

struct yedge {
    int _y;
    int _is_top;
    int _i_rect;
    yedge(int y, int is_top, int i_rect) :
        _y(y), _is_top(is_top), _i_rect(i_rect) {} 
};

int main() {
    vector<rect> rcts; // vector that stores rectangles
    vector<xedge> xes; // left and right edges of the rectangles
    int x1, x2, y1, y2;
    int i = 0;
    while (cin >> x1 >> x2 >> y1 >> y2) {
        rcts.push_back(rect(x1, x2, y1, y2));
        xes.push_back(xedge(x1, 1, i));
        xes.push_back(xedge(x2, 0, i));
        i++;
    }

    // sort left and right rectangles according to their x-coordinates
    sort(xes.begin(), xes.end(), 
        [](const xedge& e1, const xedge& e2) {
            if (e1._x != e2._x) return e1._x < e2._x;
            else if (e1._is_left != e2._is_left) 
                return e1._is_left > e2._is_left;
            else return e1._i_rect < e2._i_rect;
        });

    // a binary search tree for top and bottom edges that overlap the "scanline"
    multimap<int, yedge> edge_map;
    for (auto& xe : xes) { // xe : "scanline"
        if (!xe._is_left) { 
            auto range = edge_map.equal_range(rcts[xe._i_rect]._y1); 
            for (auto iter = range.first; iter != range.second; ++iter) {
                if (iter->second._i_rect == xe._i_rect) {
                    edge_map.erase(iter);
                    break;
                }
            }
            range = edge_map.equal_range(rcts[xe._i_rect]._y2); 
            for (auto iter = range.first; iter != range.second; ++iter) {
                if (iter->second._i_rect == xe._i_rect) {
                    edge_map.erase(iter);
                    break;
                }
            }
        } else {
            int y1 = rcts[xe._i_rect]._y1;
            int y2 = rcts[xe._i_rect]._y2;
            auto iter1 = edge_map.lower_bound(y1);
            auto iter2 = edge_map.upper_bound(y2);
            for (auto iter = iter1; iter != iter2; ++iter) {
                cout << xe._i_rect << " " << iter->second._i_rect << endl;
            }
            edge_map.insert(make_pair(y1, yedge(y1, 0, xe._i_rect)));
            edge_map.insert(make_pair(y2, yedge(y2, 1, xe._i_rect)));
        }
    }

    return 0;
}