Question: I added video ads for an android game, but it must be verified by PHP before the points can be added but I didn't find anyway to check it.

Answer: 
I'll suggest a solution that may not be the faster but should do the job.

The idea is to place each of your rectangles one by one. Everytime you add a rectangle in the map, check if it intersects any of the others. If it does, then just break these both rectangles into the correct corresponding new rectangles, depending on the shape of the intersection.

[![enter image description here](https://i.stack.imgur.com/Ch5Z2.png)](https://i.stack.imgur.com/Ch5Z2.png)

It's easy to see that if a new rectangle (green) covers the whole affected rectangle (red), only the new would be broke apart. Otherwise, both will.

Just by adding one by one and breaking them apart correctly, you will have your full set of rectangles in the end, which you just need to iterate to find your "maximal", if it means the ones with biggest area.

This algorithm should be something around O(n²) where n is the number of rectangles you add.
You can do this with simple interval algebra. For illustration, I'll put some numbers on the example you gave us. I'll use the Cartesian first quadrant, origin in the lower-left corner. The entire field is then (0, 0) to (30, 20); rectangles have corners at (10, 0) to (30, 8); (0, 12) to (13, 20); (20, 15) to (25, 17).

To solve this, group rectangle edges by their orientation with respect to their rectangles; specifically, which direction they face (away from the rectangle's center). Edges of the window face inward. This gives us four sets, one for each "facing" direction. An edge is described with the common coordinate in one direction and a range in the other. I'll keep them in the same x-y notation. For instance, sorted by y-coordinate:

```
             bottom      low-rt       up-rt
face_up   = (0-10, 0), (10-30, 8), (20-25, 17)

```

The top edge of the top rectangle coincides with the top of the window; it faces up,. but has no room for a white rectangle.

Similarly, the down-facing edges are

```
              up-left      up-rt        top
face_down = (0-13, 12), (20-25, 15), (13-30, 20)

```

Now it's a simple matter to match each rectangle edge with the first one that blocks its open region. For instance, consider the low-rt rectangle's face\_up edge, (10-30, 8) We compare to face\_down edges in order of y-coordinate, starting with y >= 8.

(0-13, 12) is the first y > 8 edge. Checking x intervals, we see that [0, 13] and [10-30] do overlap; we have a block with corners at (10, 8) and (12, 13) to expand sideways in each direction. This results in your blue rectangle.

Similarly, we will match the (face\_up) left side of the window bottom with the same face\_down edge. This results in your orange rectangle. Then we match the top of the up-rt (smallest) rectangle with the window top: green rectangle.

**Continuing** in the opposite direction, we find that two face\_down edges match existing rectangles. We also match the bottom of the up-rt rectangle with the top of the low-rt rectangle, yielding the yellow rectangle.

Repeat this process with the face\_left and face\_right edges to obtain the red and purple rectangles, as well as a second hit of the orange rectangle.

---

Is that enough of an outline for you to implement?

Sorting the edges in order gives us the ability to do a linear search from each edge. If I'm casting this code properly, the result is an **O(N)** algorithm for **N** rectangles, although the original edge sorting is **O(log N)**.