I have 2 arrays that contain starting and ending ranges.

int[] start = {1, 3, 4};
int[] end = {6, 10, 5};

Now, I want to loop through their ranges in such a way that all the values of the array must be covered. For example:

if(i==0) start = 1, end=6
we should take values 1...3 because 4..6 will be covered in next step
if(i==1) start = 3 end = 10
we should take value from 6...10 because 4 and 5 is covered in next range
if(i==2) start=4 end = 5
we should take value 4,5 which will complete the whole range  

As you can see from the above example, we have covered all the values of the array while also covering the range which is 1...10 in this case.

So, any idea how can I implement it?

CodePudding user response：

What I'd do is spell out the ranges of each step, then going backwards, remove the later ranges from earlier ranges and remove the beginning of the range if it is non consecutive.

import java.util.*;

public class ExclusionForwardBack {

    static void compute(int[] start, int[] end, List<List<Integer>> results) {
        for (int i = 0; i < start.length; i  ) {
            List<Integer> step = new ArrayList<>();
            for (int j = start[i]; j <= end[i]; j  ) {
                step.add(j);
            }
            results.add(step);
        }
        
        for (int i = start.length - 2; i >= 0; i--) {
            for (int j = i; j >= 0; j--) {
                results.get(j).removeAll(results.get(i   1));
            }
            
            List<Integer> current = results.get(i);
            for (int j = 0; j < current.size() - 1; j  ) {
                if (current.get(j)   1 != current.get(j   1)) {
                    for (int k = j; k >= 0; k--) {
                        current.remove(k);
                    }
                    break;
                }
            }
        }
    }
    
    static void print(List<List<Integer>> results) {
        for (int i = 0; i < results.size(); i  ) {
            System.out.println("Step "   i);
            for (int j : results.get(i)) {
                System.out.println("  "   j);
            }
        }
    }
    
    public static void main(String[] args) {
        int[] start1 = {1, 3, 4};
        int[] end1 = {6, 10, 5};

        List<List<Integer>> results1 = new ArrayList<>();
        
        compute(start1, end1, results1);
        print(results1);

        int[] start2 = {1, 4, 8, 12};
        int[] end2 = {5, 9, 14, 15};

        System.out.println("=======================");
        
        List<List<Integer>> results2 = new ArrayList<>();
        
        compute(start2, end2, results2);
        print(results2);

        System.out.println("=======================");

        int[] start3 = {1, 3, 5};
        int[] end3 = {6, 10, 6};

        List<List<Integer>> results3 = new ArrayList<>();
        
        compute(start3, end3, results3);
        print(results3);    
    }
}

For your two examples, this prints:

Step 0
  1
  2
  3
Step 1
  6
  7
  8
  9
  10
Step 2
  4
  5
=======================
Step 0
  1
  2
  3
Step 1
  4
  5
  6
  7
Step 2
  8
  9
  10
  11
Step 3
  12
  13
  14
  15
=======================
Step 0
  1
  2
  3
  4
Step 1
  7
  8
  9
  10
Step 2
  5
  6