Combine a set of "ranges" to find least number of ranges

Question

Given a set of ranges with lower bound and upper bound, I need to combine these ranges to produce minimum number of ranges which will cover all the values in the original set and nothing else.

Example 1:

Input:

[100, 200], [120-170],[210 - 230]

Output:

[100-200], [210-230]

Example 2:

Input:

[100, 200], [120-210],[210 - 230]

Output:

[100-230]

This is what I have so far. This program works as expected and prints out the results as expected. But I'm wondering if there is any better way to do it.

public class Range {
 public static void main(String[] args) {
 int[][] Ranges1 = new int[][] { new int[] { 94133, 94133 },
 new int[] { 94226, 94399 },
 new int[] { 94200, 94299 }
 };
 Range Range = new Range();
 int[][] normalizedRanges = Range.getTheNormalizedRanges(Ranges1);
 System.out.println("Normalized range:");
 Range.print(normalizedRanges);
 }
 private int[][] getTheNormalizedRanges(int[][] RangesToNormalize) {
 int[][] newrange = new int[RangesToNormalize.length][];
 boolean[] rangePurged = new boolean[RangesToNormalize.length];
 int newIndex = 0;
 this.sortRange(RangesToNormalize);
 for (int i = 0; i < RangesToNormalize.length; i++) {
 if (rangePurged[i])
 continue;
 if (i == (RangesToNormalize.length - 1) ){
 newrange[newIndex] = RangesToNormalize[i];
 break;
 }
 int min = RangesToNormalize[i][0];
 int max = RangesToNormalize[i][1];
 int nextMin = RangesToNormalize[i + 1][0];
 int nextMax = RangesToNormalize[i + 1][1];
 if (max >= nextMin) {
 if (max >= nextMax)
 newrange[newIndex] = new int[] { min, max };
 else
 newrange[newIndex] = new int[] { min, nextMax };
 //keep track of the ranges that are purged from the original list.
 rangePurged[i+1] = true;
 } else {
 //if there is no overlap, add the current range to the new list
 newrange[newIndex] = RangesToNormalize[i];
 }
 newIndex++;
 }
 return newrange;
 }
 private void print(int[][] printRange){
 if(printRange == null || printRange.length <=0)
 throw new IllegalArgumentException("printRange is empty or null");
 for (int i = 0; i < printRange.length; i++) {
 if (printRange[i] != null)
 { 
 System.out.println("["+ printRange[i][0] + ", "
 + printRange[i][1]+"]");
 }
 }
 }
 private void sortRange(int[][] rangeToSort){
 Arrays.sort(rangeToSort, new Comparator<int[]>() {
 @Override
 public int compare(int[] range1, int[] range2) {
 int range1Min = range1[0];
 int range2Min = range2[0];
 if (range1Min > range2Min)
 return 1;
 if (range1Min < range2Min)
 return -1;
 return 0;
 }
 });
 }
 }

• h.j.k.: Related: codereview.stackexchange.com/questions/85089/…
• Malachi: you should not remove the code
• Gerold Broser: And rejecting my edit that restored it and removed the bunch of unnecessary empty lines in addition doesn't increase my motivation to bother with this any longer.

Answer 1

The program is NOT working as expected. You can see the bug if you give it the following input

 int[][] zipRanges1 = new int[][] { 
 new int[] { 1, 5 },
 new int[] { 2, 6 }, 
 new int[] { 3, 4 }
 };

The problem is that you compare ranges from the input only. The correct logic is that for each input range, you should iterate over newZipRanges and "insert" the current input in the correct place. You sohuld make the Logic to normalize the zipcode range piece of code into a method that compares and possibly merges two ranges.

However, the story does not end here. after the above processing is done (after you finish iterating over the input), you will need to iterate over the newZipRanges and normalize it. consider the following case:

newZipRanges contains {1, 4}, {7, 9} and now the input range you're processing is {1, 8} you will merge it into the first new range and produce newZipRanges == {1, 8}, {7, 9} which obviously needs normalizing. I think after any modification to newZipRanges (after merging an input range into it) you need to iterate over the newZipRanges and see if any merging needs to be done (perhaps sorting every time? not sure)

one last advice, to merge overlapping ranges, use Math.min on the lower bounds and Math.max on the upper bounds. its nicer than the if question you have.