public static List<IntPair> intersectSortedRangeSets(List<List<IntPair>> sortedRangeSetList) {
    if (sortedRangeSetList == null || sortedRangeSetList.isEmpty()) {
      return Collections.emptyList();
    }
    if (sortedRangeSetList.size() == 1) {
      return sortedRangeSetList.get(0);
    }
    // if any list is empty return empty
    for (List<IntPair> rangeSet : sortedRangeSetList) {
      if (rangeSet.isEmpty()) {
        return Collections.emptyList();
      }
    }
    int[] currentRangeSetIndex = new int[sortedRangeSetList.size()];
    Arrays.fill(currentRangeSetIndex, 0);
    int maxHead = -1;
    int maxHeadIndex = -1;
    boolean reachedEnd = false;
    List<IntPair> result = new ArrayList<IntPair>();
    while (!reachedEnd) {
      // find max Head in the current pointers
      for (int i = 0; i < sortedRangeSetList.size(); i++) {
        int head = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]).getLeft();
        if (head > maxHead) {
          maxHead = head;
          maxHeadIndex = i;
        }
      }
      // move all pointers forward such that range they point to contain maxHead
      int j = -1;
      while (j++ < sortedRangeSetList.size() - 1) {
        if (j == maxHeadIndex) {
          continue;
        }
        boolean found = false;
        while (!found && currentRangeSetIndex[j] < sortedRangeSetList.get(j).size()) {
          IntPair range = sortedRangeSetList.get(j).get(currentRangeSetIndex[j]);
          if (maxHead >= range.getLeft() && maxHead <= range.getRight()) {
            found = true;
            break;
          }
          if (range.getLeft() > maxHead) {
            maxHead = range.getLeft();
            maxHeadIndex = j;
            j = -1;
            break;
          }
          currentRangeSetIndex[j] = currentRangeSetIndex[j] + 1;
        }
        // new maxHead found
        if (j == -1) {
          continue;
        }
        if (!found) {
          reachedEnd = true;
          break;
        }
      }

      if (reachedEnd) {
        break;
      }
      // there is definitely some intersection possible here
      IntPair intPair = sortedRangeSetList.get(0).get(currentRangeSetIndex[0]);
      IntPair intersection = Pairs.intPair(intPair.getLeft(), intPair.getRight());
      for (int i = 1; i < sortedRangeSetList.size(); i++) {
        IntPair pair = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]);
        int start = Math.max(intersection.getLeft(), pair.getLeft());
        int end = Math.min(intersection.getRight(), pair.getRight());
        intersection.setLeft(start);
        intersection.setRight(end);
      }
      if (!result.isEmpty()) {
        // if new range is contiguous merge it
        IntPair prevIntersection = result.get(result.size() - 1);
        if (intersection.getLeft() == prevIntersection.getRight() + 1) {
          prevIntersection.setRight(intersection.getRight());
        } else {
          result.add(intersection);
        }
      } else {
        result.add(intersection);
      }
      // move the pointers forward for rangesets where the currenttail == intersection.tail
      for (int i = 0; i < sortedRangeSetList.size(); i++) {
        IntPair pair = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]);
        if (pair.getRight() == intersection.getRight()) {
          currentRangeSetIndex[i] = currentRangeSetIndex[i] + 1;
          if (currentRangeSetIndex[i] == sortedRangeSetList.get(i).size()) {
            reachedEnd = true;
            break;
          }
        }
      }
    }
    return result;
  }
@Test
  public void testRandom() {
    int totalDocs = 1_000_000;
    int maxRange = 10000;
    int minRange = 1000;
    long randomSeed = System.currentTimeMillis();
    Random r = new Random(randomSeed);
    int numLists = 3;
    List<List<IntPair>> sortedRangePairsList = new ArrayList<>();
    List<Set<Integer>> rawIdSetList = new ArrayList<>();
    for (int i = 0; i < numLists; i++) {
      List<IntPair> pairs = new ArrayList<>();
      Set<Integer> rawIdSet = new HashSet<>();
      int docId = 0;
      while (docId < totalDocs) {
        int start = docId + r.nextInt(maxRange);
        int end = start + Math.max(minRange, r.nextInt(maxRange));
        if (end < totalDocs) {
          pairs.add(Pairs.intPair(start, end));
          for (int id = start; id <= end; id++) {
            rawIdSet.add(id);
          }
        }
        docId = end + 1;
      }
      sortedRangePairsList.add(pairs);
      rawIdSetList.add(rawIdSet);
    }
    // expected intersection
    List<IntPair> expected = new ArrayList<>();
    int tempStart = -1;
    for (int id = 0; id < totalDocs; id++) {
      boolean foundInAll = true;
      for (int i = 0; i < numLists; i++) {
        if (!rawIdSetList.get(i).contains(id)) {
          foundInAll = false;
          break;
        }
      }
      if (foundInAll) {
        if (tempStart == -1) {
          tempStart = id;
        }
      } else {
        if (tempStart != -1) {
          expected.add(Pairs.intPair(tempStart, id - 1));
          tempStart = -1;
        }
      }
    }
    List<IntPair> actual = SortedRangeIntersection.intersectSortedRangeSets(sortedRangePairsList);

    if (!actual.equals(expected)) {
      LOGGER.error("Actual pairs not equal to expected pairs.");
      LOGGER.error("Actual pairs: {}", actual);
      LOGGER.error("Expected pairs: {}", expected);
      LOGGER.error("Random seed: {}", randomSeed);
      LOGGER.error("Sorted range pairs list: {}", sortedRangePairsList);
      Assert.fail();
    }
  }