Click here to Skip to main content
15,920,513 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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
Comments
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.

1 solution

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.
 
Share this answer
 
Comments
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    
What is your time complexity?
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

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900