Find the largest interval of non-intersecting roads

This is the problem I'm trying to solve.

Suppose you have two main roads A and B that are parallel to each other. Now we have a number of R roads that all have one endpoint on A and another endpoint on B. None of the roads in R have an endpoint on any road. So if r is expensive in R, then there are 2r different endpoints. In addition, these roads can stretch, however, for a long time, go diagonally, parallel or in any direction they like, until it starts and ends on radars A and B. Suppose we can check if two roads intersect at flow O (1).

Q1) Find the largest continuous subset of roads in R in which two roads that do not intersect do not intersect. This algorithm should run in O (n log n)

Q2) Same as Q1, but now we will assume that 2r different endpoints lie on the unit circle given by x 2 + y 2 = 1

This algorithm should work in O (n 3 ) or less.

My approaches so far. I tried sorting the roads by at least 2 endpoints for q1, so we have roads starting from the leftmost one at the beginning. Then I will go through them and check only if there are roads whose minimum of their two endpoints starts after the iterative road, bypassing the endpoint, and they reset these roads and call the function recursively.

But I'm not sure how this works. And I'm not sure if its O (n log n)

For q2, I have no idea.

I have a feeling that this can be done using dynamic programming, and I'm missing some kind of data structure with which I could easily solve this problem. Please, help.

+3
source share
1 answer

QUESTION 1

You have N endpoints on road A and N endpoints on road B.

Sort the roads in R based on their first endpoint and prepare a list A of their second endpoints.

So, for example, if we have roads:

1->10
8->7
5->6

we will sort them by the first endpoint in:

1->10
5->6
8->7

and prepare list A with the second endpoints:

A = [10,6,7]

.

O (nlogn).

[6,7] 2, 2.

enter image description here

+2

All Articles