Best Data Structure to solve this problem

[danial leksevo]

Hi All,

Could you please suggest me which data structure is best to use to solve this problem


I have set of int ranges in the form of two dimensional array e.g int[][] array= {{1- 4},{6-10}{8-20},{20- 30},{50-60}};

I want to combining ranges wherever possible to make a range which cover all of sub-set of the ranges e.g {{6-10}{8-20},{20- 30}}={6-30}

and my final set of ranges will be like array= {{1- 4},{6-30},{50-60}}


Thanks in advance!

[Marty Groban]

I would try to use a doubly linked list.

[Jim Hoglund]

You could, 1) add each individual value to a Set. This would
eliminate any duplicates. Then 2) sort the set, and 3) scan
the set to formulate the new ranges.

Jim ... ...

[danial leksevo]

Thanks Jim,

[Jim Hoglund]

Yes, you're on the right track. If the Set is sorted on Integer, you can
just look for a missing value to find the end of a range. Give it a try.

Jim ... ...

[Stephan van Hulst]

Maybe you should create a Range class. You can then write a utility method

public static Set<Range> normalize(Set<Range> ranges) {
  // assuming the set is sorted by lower range
  // for each range R(i) in the set, see if it intersects with the range R(i-1) 
  // if it doesn't, start a new range Q with the same bounds as R(i) and add it to the result set
  // if it does, set the upper bound of Q to the upper bound of R(i), if it's greater.
}