15,920,513 members
See more:
I have a solution the problem, Given n rectangles (n <= 10^5), each rectangle input is represented by two lines inputs, the first line is of the low left point, and the second of the upper right point, (x,y) (-1000 <= x, y <= 1000). You have to find the maximum of rectangle intersections.

The code is the following, it works a bit fast, but the online judge of my school I am submitting this code too, fails at the last test case for time limit constraints. I don't know how to optimize it any more.

Doing a nested loop to check each rectangle proved to be asymptotically not suitable, given time limit 1s, and memory 256MB.

Sample Input:

2

1 1

2 2

3 3

4 4

Output:

0

Sample Input:

4

1 4

9 6

2 1

6 3

3 1

7 6

5 4

7 8

Output:

3

What I have tried:

C++
```//#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
//#include <cmath>
//#include <climits>
//#include <string>
#include <algorithm>

using namespace std;

struct Edge {
enum Type
{
BEGIN,
END
};

Type type;
int abscissa;
int top;
int bottom;
};

struct Segment {
int begin;
int end;
unsigned int intersections = 0;
};

bool operator<(Edge const& e1, Edge const& e2) {
return e1.abscissa < e2.abscissa || (e1.abscissa == e2.abscissa && e1.type < e2.type);
}

bool operator<(Segment const& s1, Segment const& s2) {
return s1.begin < s2.begin;
}

bool operator==(Segment const& s1, Segment const& s2) {
return s1.begin == s2.begin;
}

//Start of edge's interval (between bottom and top) in segments via binary search
Segment* binary_search(Segment* Begin, Segment* End, int bottom) {

while (End - Begin > 1) {

auto mid = Begin + (End - Begin) / 2;

if (mid->end == bottom) {
return mid;
}

else if (mid->end < bottom)
Begin = mid + 1;

else
End = mid;
}
return Begin;
}

int main() {

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

int n, res = 0;
cin >> n;

Edge* edges = new Edge[2 * n];
Segment* segments = new Segment[2 * n];

for (int i = 0; i < n; i++) {
int left, right, bottom, top;
cin >> left >> bottom >> right >> top;

edges[2 * i].type = Edge::BEGIN;
edges[2 * i].abscissa = left;
edges[2 * i].bottom = bottom;
edges[2 * i].top = top;
edges[2 * i + 1].type = Edge::END;
edges[2 * i + 1].abscissa = right;
edges[2 * i + 1].top = top;
edges[2 * i + 1].bottom = bottom;

segments[i * 2].begin = segments[i * 2].end = bottom;
segments[i * 2 + 1].begin = segments[i * 2 + 1].end = top;
}

sort(edges, edges + 2 * n);
sort(segments, segments + 2 * n);

auto end = unique(segments, segments + 2 * n);

for (auto i = segments + 1; i != end; i++)
i[-1].end = i->begin;

end--;
for (int i = 0; i < 2 * n; i++) {// iterate over the edges

auto current = binary_search(segments, end, edges[i].bottom);

while (current != end && current->end <= edges[i].top) {

if (edges[i].type == Edge::BEGIN) {

current->intersections++;

if (current->intersections > res)
res = current->intersections;
}
else
current->intersections--;

current++;
}
}

if (res == 1)
cout << 0;
else
cout << res;

return 0;
}```
Posted
Updated 2-Jan-20 21:13pm
v3
Patrice T 2-Jan-20 14:39pm
Would be nice to give exact requirement and a sample input and expected result.
Jiopik 2-Jan-20 14:50pm
I have provided it. Insead of going to segment trees. Is there a way to improve as it is now.

## Solution 1

Quote:
The code is the following, it works a bit fast, but the online judge of my school I am submitting this code too, fails at the last test case for time limit constraints.

With today computers, about any code "works a bit fast" with a small dataset, it doesn't mean that the code is efficient because problems appears with large datasets.
Quote:
I don't know how to optimize it any more.

Your code look a little over engineered to me. I don't see any reason to do this way.
My approach would be strait forward, no edges or segments, but instead, a simple list of rectangles and with any new rectangle, check if intersect with a previous one.
It is brute force, but look simpler to me.

Rick York 3-Jan-20 1:24am
I agree with Patrice. There is no need for search or sorting with such a small data set. Brute force comparisons would be the best option I think.
Jiopik 3-Jan-20 3:14am
I agree it would be over engineered if the n <= 10^4. But it's not. And maybe you had to see that even with such algorithm, the time limit still could not be passed. Any suggestion.
Patrice T 3-Jan-20 6:29am
With my approach, for n rectangles, you iterate n*(n-1)/2 times, about (n^2)/2.
Since you break a rectangles in 2 edges/segments, and supposing the binary search is efficient, i expect your code to iterate in 2n*(2n-1)/2 steps, about (4n^2)/2.
Not sure my approach is not faster.
Jiopik 3-Jan-20 9:23am
Patrice T 3-Jan-20 11:11am
Number of rectangles to check in inner loop.
for any rectangle x, there is x-1 rectangle check in inner loop.
if 10 rectangles, checks are 0+1+2+3+4+5+6+7+8+9
This suite is up to y is y*(y+1)/2