Given n horizontal segments, where the range of each segment is x2 - x1, what algorithm should i apply to get a straight line that gets me the biggest combined range (every intersection with a segment adds the range of that segment), its like finding a line to drill with, to get the maximum amount of water (water representing segments with X2-X1 quantity) I completed the brute force algorithm with a depressing big O (n^4)
0
votes
can you explain your brute force?
– juvian
@juvian i basically went through all possible lines taking X amount of points from each segment and linking it to other X amount of points for every other segment, inside the loop, i call a function that checks the intersections with the array of segments, if the line intersects with a segment[n] it accumulates the range and checks if it is higher than the current max.
– Marcel.af
1 Answers
0
votes
I will assume there is no segment that starts on the end of another, if not will need to modify a bit the following:
- For each segment, create 2 tuples: (x1, index) and (x2, index)
- Sort the tuples by its first value
- Set best = 0
- Iterate tuples. If its the start point (index wasn't seen before), add its value (x2 - x1) to best. If its an end point, substracts its value to best.
- The answer to the problem will be the highest value best reached.
Complexity: O(n log n)
