How to find the point that gives the maximum value fast? Java or c++ code please

user_13879370 0
Viewed 285

I need a fast way to find maximum value when intervals are overlapping, unlike finding the point where got overlap the most, there is "order". I would have int[][] data that 2 values in int[], where the first number is the center, the second number is the radius, the closer to the center, the larger the value at that point is going to be. For example, if I am given data like:

int[][] data = new int[][]{
{1, 1},
{3, 3},
{2, 4}};

Then on a number line, this is how it's going to looks like:

x axis: -2 -1 0 1 2 3 4 5 6 7  
   1 1:       1 2 1  
   3 3:       1 2 3 4 3 2 1  
   2 4:  1  2 3 4 5 4 3 2 1

So for the value of my point to be as large as possible, I need to pick the point x = 2, which gives a total value of 1 + 3 + 5 = 9, the largest possible value. It there a way to do it fast? Like time complexity of O(n) or O(nlogn)

linear-programming math geometry c++ java
2 Answers

This can be done with a simple O(n log n) algorithm.

Consider the value function v(x), and then consider its discrete derivative dv(x)=v(x)-v(x-1). Suppose you only have one interval, say {3,3}. dv(x) is 0 from -infinity to -1, then 1 from 0 to 3, then -1 from 4 to 6, then 0 from 7 to infinity. That is, the derivative changes by 1 "just after" -1, by -2 just after 3, and by 1 just after 6.

For n intervals, there are 3*n derivative changes (some of which may occur at the same point). So find the list of all derivative changes (x,change), sort them by their x, and then just iterate through the set.

Behold:

intervals = [(1,1), (3,3), (2,4)]

events = []
for mid, width in intervals:
    before_start = mid - width - 1
    at_end = mid + width
    events += [(before_start, 1), (mid, -2), (at_end, 1)]

events.sort()

prev_x = -1000
v = 0
dv = 0

best_v = -1000
best_x = None

for x, change in events:
    dx = x - prev_x
    v += dv * dx
    if v > best_v:
        best_v = v
        best_x = x
    dv += change
    prev_x = x

print best_x, best_v

And also the java code:

 TreeMap<Integer, Integer> ts = new TreeMap<Integer, Integer>();
        
    for(int i = 0;i<cows.size();i++) {
        int index = cows.get(i)[0] - cows.get(i)[1];
        if(ts.containsKey(index)) {
            ts.replace(index, ts.get(index) + 1);
        }else {
            ts.put(index, 1);
        }
            
        index = cows.get(i)[0] + 1;
        if(ts.containsKey(index)) {
            ts.replace(index, ts.get(index) - 2);
        }else {
            ts.put(index, -2);
        }
            
        index = cows.get(i)[0] + cows.get(i)[1] + 2;
        if(ts.containsKey(index)) {
            ts.replace(index, ts.get(index) + 1);
        }else {
                ts.put(index, 1);
        }
    }
        
    int value = 0;
    int best = 0;
    int change = 0;
    int indexBefore = -100000000;
        
    while(ts.size() > 1) {
        int index = ts.firstKey();
        value += (ts.get(index) - indexBefore) * change;
        best = Math.max(value, best);
        change += ts.get(index);
        ts.remove(index);
    }

where cows is the data

user_7874800

Hmmm, a general O(n log n) or better would be tricky, probably solvable via linear programming, but that can get rather complex.

After a bit of wrangling, I think this can be solved via line intersections and summation of function (represented by line segment intersections). Basically, think of each as a triangle on top of a line. If the inputs are (C,R) The triangle is centered on C and has a radius of R. The points on the line are C-R (value 0), C (value R) and C+R (value 0). Each line segment of the triangle represents a value.

Consider any 2 such "triangles", the max value occurs in one of 2 places:

  • The peak of one of the triangle
  • The intersection point of the triangles or the point where the two triangles overall. Multiple triangles just mean more possible intersection points, sadly the number of possible intersections grows quadratically, so O(N log N) or better may be impossible with this method (unless some good optimizations are found), unless the number of intersections is O(N) or less.

To find all the intersection points, we can just use a standard algorithm for that, but we need to modify things in one specific way. We need to add a line that extends from each peak high enough so it would be higher than any line, so basically from (C,C) to (C,Max_R). We then run the algorithm, output sensitive intersection finding algorithms are O(N log N + k) where k is the number of intersections. Sadly this can be as high as O(N^2) (consider the case (1,100), (2,100),(3,100)... and so on to (50,100). Every line would intersect with every other line. Once you have the O(N + K) intersections. At every intersection, you can calculate the the value by summing the of all points within the queue. The running sum can be kept as a cached value so it only changes O(K) times, though that might not be posible, in which case it would O(N*K) instead. Making it it potentially O(N^3) (in the worst case for K) instead :(. Though that seems reasonable. For each intersection you need to sum up to O(N) lines to get the value for that point, though in practice, it would likely be better performance.

There are optimizations that could be done considering that you aim for the max and not just to find intersections. There are likely intersections not worth pursuing, however, I could also see a situation where it is so close you can't cut it down. Reminds me of convex hull. In many cases you can easily reduce 90% of the data, but there are cases where you see the worst case results (every point or almost every point is a hull point). For example, in practice there are certainly causes where you can be sure that the sum is going to be less than the current known max value.

Another optimization might be building an interval tree.

user_16082260
Related