CODEWITHSUNDEEP
javaguava
Ashok
Ashok

Reputation: 71

Intersecting ranges when using RangeMap

I came across a problem like

You are maintaining a trading platform for a hedge fund. Traders in your hedge fund execute trading strategies throughout the day. For the sake of simplicity let's assume that each trading strategy makes i pounds/minute for as long as it's running. i can be negative. In the end of the day you have a log file that looks as follows:

Each line represents when the strategy started executing, when it stopped, and the income produced as a rate. Write some code to return the time during the day when the hedge fund was making the highest amount of money per minute.

Examples:

Input:

Result :

Input:

Result:

Input:

Result:

I have been trying to use guava RangeMap to solve it, but there is no apparent way to intersect the overlapping intervals.

For example:

private static void method(Record[] array){
    RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
    for (Record record : array) {
        rangeMap.put(Range.closed(record.startTime, record.endTime), record.profitRate);
    }
    System.out.println(rangeMap);   
}

public static void main(String[] args) {
    Record[] array = {new Record(1,13,400), new Record(10,20,100)};
    method(array);
}

And the map looks like: [[1..10)=400, [10..20]=100]

Is there any way to override the overlap behavior or any other data structure that can be used to solve the problem?

Upvotes: 3

Views: 3028

Answers (2)

Louis Wasserman
Louis Wasserman

Reputation: 198491

Use RangeMap.subRangeMap(Range) to identify all the existing range entries intersecting with some other particular range, which will allow you to filter out the intersections.

This might look something like:

void add(RangeMap<Integer, Integer> existing, Range<Integer> range, int add) {
  List<Map.Entry<Range<Integer>, Integer>> overlaps = new ArrayList<>(
      existing.subRangeMap(range).asMapOfRanges().entrySet());
  existing.put(range, add);
  for (Map.Entry<Range, Integer> overlap : overlaps) {
    existing.put(overlap.getKey(), overlap.getValue() + add);
  }
}

Upvotes: 3

Marco13
Marco13

Reputation: 54709

As mentioned in the comments: A RangeMap is probably not suitable for this, because the ranges of a RangeMap have to be disjoint.

One approach for solving this in general was mentioned in the comments: One could combine all the ranges, and generate all disjoint ranges from that. For example, given these ranges

  |------------|       :400
           |----------|:100

one could compute all sub-ranges that are implied by their intersections

  |--------|           :400
           |---|       :500
               |------|:100

Where the range in the middle would obviously be the solution in this case.

But in general, there are some imponderabilities in the problem statement. For example, it is not entirely clear whether multiple ranges may have the same start time and/or the same end time. Things that may be relevant for possible optimizations may be whether the records are "ordered" in any way.

But regardless of that, one generic approach could be as follows:

  • Compute a mapping from all start times to the records that start there
  • Compute a mapping from all end times to the records that end there
  • Walk through all start- and end times (in order), keeping track of the accumulated profit rate for the current interval

(Yes, this is basically the generation of the disjoint sets from the comments. But it does not "construct" a data structure holding this information. It just uses this information to compute the maximum, on the fly).

An implementation could look like this:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.Set;
import java.util.TreeSet;

class Record
{
    int startTime;
    int endTime;
    int profitRate;

    public Record(int startTime, int endTime, int profitRate)
    {
        this.startTime = startTime;
        this.endTime = endTime;
        this.profitRate = profitRate;
    }

    @Override
    public String toString()
    {
        return "(" + startTime + "..." + endTime + ", " + profitRate + ")";
    }

}

public class MaxRangeFinder
{
    public static void main(String[] args)
    {
        test01();
        test02();
    }

    private static void test01()
    {
        System.out.println("Test case 01:");
        Record[] records = {
            new Record(1,13,400), 
            new Record(10,20,100),
        };
        Record max = computeMax(Arrays.asList(records));
        printNicely(Arrays.asList(records), max);
    }

    private static void test02()
    {
        System.out.println("Test case 02:");
        Record[] records = {
            new Record(1,5,100), 
            new Record(2,6,200),
            new Record(3,4,50),
            new Record(3,4,25),
            new Record(5,8,200),
        };
        Record max = computeMax(Arrays.asList(records));
        printNicely(Arrays.asList(records), max);
    }


    private static Record computeMax(Collection<? extends Record> records)
    {
        // Create mappings from the start times to all records that start 
        // there, and from the end times to the records that end there 
        Map<Integer, List<Record>> recordsByStartTime =
            new LinkedHashMap<Integer, List<Record>>();
        for (Record record : records)
        {
            recordsByStartTime.computeIfAbsent(record.startTime,
                t -> new ArrayList<Record>()).add(record);
        }
        Map<Integer, List<Record>> recordsByEndTime =
            new LinkedHashMap<Integer, List<Record>>();
        for (Record record : records)
        {
            recordsByEndTime.computeIfAbsent(record.endTime,
                t -> new ArrayList<Record>()).add(record);
        }

        // Collect all times where a record starts or ends
        Set<Integer> eventTimes = new TreeSet<Integer>();
        eventTimes.addAll(recordsByStartTime.keySet());
        eventTimes.addAll(recordsByEndTime.keySet());

        // Walk over all events, keeping track of the 
        // starting and ending records
        int accumulatedProfitRate = 0;
        int maxAccumulatedProfitRate = -Integer.MAX_VALUE;
        int maxAccumulatedProfitStartTime = 0;
        int maxAccumulatedProfitEndTime = 0;

        for (Integer eventTime : eventTimes)
        {
            int previousAccumulatedProfitRate = accumulatedProfitRate;

            // Add the profit rate of the starting records
            List<Record> startingRecords = Optional
                .ofNullable(recordsByStartTime.get(eventTime))
                .orElse(Collections.emptyList());
            for (Record startingRecord : startingRecords)
            {
                accumulatedProfitRate += startingRecord.profitRate;
            }

            // Subtract the profit rate of the ending records
            List<Record> endingRecords = Optional
                .ofNullable(recordsByEndTime.get(eventTime))
                .orElse(Collections.emptyList());
            for (Record endingRecord : endingRecords)
            {
                accumulatedProfitRate -= endingRecord.profitRate;
            }

            // Update the information about the maximum, if necessary
            if (accumulatedProfitRate > maxAccumulatedProfitRate)
            {
                maxAccumulatedProfitRate = accumulatedProfitRate;
                maxAccumulatedProfitStartTime = eventTime;
                maxAccumulatedProfitEndTime = eventTime;
            }
            if (previousAccumulatedProfitRate == maxAccumulatedProfitRate &&
                accumulatedProfitRate < previousAccumulatedProfitRate)
            {
                maxAccumulatedProfitEndTime = eventTime;
            }
        }

        return new Record(
            maxAccumulatedProfitStartTime, 
            maxAccumulatedProfitEndTime, 
            maxAccumulatedProfitRate);

    }



    private static void printNicely(
        Collection<? extends Record> records, 
        Record max)
    {
        StringBuilder sb = new StringBuilder();
        int maxEndTime =  Collections.max(records, 
            (r0, r1) -> Integer.compare(r0.endTime, r1.endTime)).endTime;
        for (Record record : records)
        {
            sb.append("     ")
                .append(createString(record, maxEndTime))
                .append("\n");
        }
        sb.append("Max: ").append(createString(max, maxEndTime));
        System.out.println(sb.toString());
    }

    private static String createString(Record record, int maxEndTime)
    {
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (i < record.startTime)
        {
            sb.append(" ");
            i++;
        }
        sb.append("|");
        while (i < record.endTime)
        {
            sb.append("-");
            i++;
        }
        sb.append("|");
        while (i < maxEndTime)
        {
            sb.append(" ");
            i++;
        }
        sb.append(":").append(record.profitRate);
        return sb.toString();
    }
}

The output for the two test cases given in the code is

Test case 01:
      |------------|       :400
               |----------|:100
Max:           |---|       :500

Test case 02:
      |----|   :100
       |----|  :200
        |-|    :50
        |-|    :25
          |---|:200
Max:      |-|  :400

Upvotes: 2

Related Questions