Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Best Data Structure to solve this problem

 
danial leksevo
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would try to use a doubly linked list.
 
Jim Hoglund
Ranch Hand
Posts: 525
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Jim,

 
Jim Hoglund
Ranch Hand
Posts: 525
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Pie
Posts: 5574
53
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Maybe you should create a Range class. You can then write a utility method
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic