1

This is not a Java specific question, but I have to implement it in Java, that is why I tagged it with Java.

The problem:

I have a List of Ranges (a Range is specified by a Stratpoint and an Endpoint in this example i simple use an int[]):

In Java:

List<int[2]> ranges = new ArrayList<>();
ranges.add(new int[]{1,100});
ranges.add(new int[]{30,95});
ranges.add(new int[]{10,60});
ranges.add(new int[]{15,25});
ranges.add(new int[]{33,66});
ranges.add(new int[]{20,50});
ranges.add(new int[]{51,100});
ranges.add(new int[]{25,70});

The output should be a Range, that is present in the most Ranges. In this chase the output would be [33,50]. Because this Range is inside of 6 Ranges from the List.

Hope you will understand my question. Thanks!

micpog90
  • 106
  • 8
  • But where is `33,50` in range list. How 6? Explain it in a brief – Nitin Bisht Jun 09 '20 at 18:03
  • 1
    Could you post the code you've tried so far, or at least describe the algorithm you were thinking of? By the way, `List` is not valid Java syntax. I think you mean `List`. Arrays in Java don't have statically determined sizes – user Jun 09 '20 at 18:03
  • 2
    I would suggest making a bunch of sets of ranges. You make a set including the first range. Then, if the second range overlaps with that first range, you add it to that first set. Otherwise, you make a new set and add the second range to that. Keep doing this for every range. For every set of ranges, if your next range overlaps with every range in that set, add it to that set. Then find the biggest set of ranges, and find the common part in that set – user Jun 09 '20 at 18:06
  • @NitinBisht The output does not have to be in the Range List. Sorry for confusion. If I take the first two Ranges for Example all Values from 30 to 95 are inside these two Ranges. If I also look at the third Range all Values from 30 to 60 are inside of that 3 Ranges...and so on – micpog90 Jun 09 '20 at 18:08
  • @user Thanks that is a good idea to start with – micpog90 Jun 09 '20 at 18:10
  • How much is the accepted gap for a range? I mean, statistically, when a range is acceptable? When it's inside 50% + 1 ranges? When it's inside 60% of the ranges? Please, clarify that. – Snix Jun 09 '20 at 18:16
  • @micpog90: can you explain why six is sufficient (here)? – Willem Van Onsem Jun 09 '20 at 19:00
  • Does this answer your question? [Find the maximally intersecting subset of ranges](https://stackoverflow.com/questions/15013800/find-the-maximally-intersecting-subset-of-ranges) – Dave Jun 11 '20 at 01:51
  • [Here is an implementation](https://stackoverflow.com/a/63902229/507738) of Dave's algorithm, in Java. Perhaps it is useful. – MC Emperor Sep 15 '20 at 14:04

1 Answers1

3

EDIT: Actually, just see this answer by @Dave, which is much more efficient.

EDIT: Unfortunately, my previous code is flawed. For example, with the below input, it outputs the range 99-100 instead of 3-50. Try the new code here.

Range(1, 100), Range(99, 100), Range(2, 50), Range(3, 90)

I wrote another algorithm, but this one is way slower and takes up more space (both time and space complexity are 2^n)

  • Make a map called rangeMap where the keys are ranges and the values are how many other ranges that range is part of (Integers)
  • For every range range in your list of ranges:
    • Create another map createdRanges, again mapping ranges to integers
    • For every entry in rangeMap
      • Define range2 and n to be the range and integer that entry holds
      • If range and range2 overlap:
        • Define newRange to be that overlapping part
        • Define newN to be n + 1, so we know that another range was overlapped by this one
        • Add newRange to createdRanges, with the value n + 1.
      • Otherwise, just continue the loop
    • Once you're done with that loop, go through every range in createdRanges.
      • If that range doesn't already exist in rangeMap, add that range and the corresponding number that says how many ranges it overlaps.
      • Otherwise, check if the value that is already in the map is less than the number of ranges this current range overlaps. If so, update that value.
  • Finally, find the entry (or entries) in rangeMap with the highest value/number of overlaps, and return the key that maps to that value.

While this is extremely inefficient, if you're going to use it for a large number of ranges, you can optimize it to be less bad by removing ranges for which there exist ranges with more overlaps (or the same number) and are less restrictive, or somehow delaying calculation of ranges, etc.

Link to repl.it

user
  • 7,435
  • 3
  • 14
  • 44
  • Thanks a lot! Excactly what I was looking for. :) – micpog90 Jun 09 '20 at 19:36
  • 1
    @micpog90 My previous algorithm was incorrect. I'm really sorry about that. I've updated it now, but it isn't very fast when you have to process a large number of ranges. I'll find a better algorithm and update it later. If this is a self-learning exercise, it probably still be sufficient though – user Jun 09 '20 at 22:10
  • 1
    thanks I really appricate it! I tried modifying your previous code, but ended up using pretty much your code. I ran it against a big amout of test data and it gave back the right result in 90% of cases.. I will try your provided new code now. Again thank you very much!!:) – micpog90 Jun 10 '20 at 23:22
  • 2
    @user https://stackoverflow.com/questions/15013800/find-the-maximally-intersecting-subset-of-ranges ? – Dave Jun 11 '20 at 02:30
  • @Dave That's a really smart way to do it! micpog90, do you want to close your question or do you still want that translated into Java? – user Jun 11 '20 at 14:26