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 testComplex() {
    String rangeSet1 = "[[9148,10636], [18560,21885], [29475,32972], [34313,37642], [38008,47157], [50962,53911], "
        + "[59240,68238], [72458,83087], [92235,97593], [100690,103101], [111708,120102], [123212,124718], "
        + "[127544,134012], [134701,141314], [144966,146889], [147206,156680], [163842,168747], [175241,179737], "
        + "[180669,184662], [192538,200004], [207255,211226], [217529,219152], [221319,228532], [230549,236908], "
        + "[237353,240840], [245097,251894], [253228,257447], [263986,268166], [272168,276416], [282756,285555], "
        + "[286030,289848], [293220,303828], [308259,317810], [320830,330498], [337606,345534], [354205,361367], "
        + "[365751,375129], [379830,382548], [390661,399509], [409031,415694], [421748,428011], [436729,442978], "
        + "[443187,448760], [454285,464404], [469128,471735], [475965,478758], [483038,491060], [496477,499410], "
        + "[502719,507364], [511478,515427], [521615,523897], [524251,529600], [530904,536822], [541666,543826], "
        + "[551652,555367], [561244,565874], [573934,582151], [587804,593424], [596533,599490], [601884,605244], "
        + "[610479,618173], [627032,630079], [633582,643323], [648357,658921], [662083,664340], [666519,677174], "
        + "[681524,687223], [693032,696329], [700808,705461], [709573,713092], [722500,732846], [733115,741189], "
        + "[742183,743217], [748442,754700], [760482,768791], [769875,773877], [774153,775538], [778521,781333], "
        + "[781945,791595], [799389,809167], [811769,814445], [824160,831582], [838445,844533], [850597,858212], "
        + "[862638,867759], [877243,887468], [893193,895091], [902608,908295], [911058,915872], [916127,917590], "
        + "[922702,933633], [938082,946932], [953197,956096], [965980,970314], [976357,983182], [983378,991764]]";
    String rangeSet2 = "[[4615,7365], [9048,19300], [25607,33900], [37975,45734], [53195,58803], [64401,72246], "
        + "[76305,84289], [86575,96695], [104465,114232], [121799,124496], [132587,137518], [146406,152055], "
        + "[154808,159304], [165855,168693], [177387,184548], [192275,202089], [204700,215167], [218780,219934], "
        + "[220492,224530], [227195,231541], [233667,241692], [249043,251396], [258494,263095], [271187,272880], "
        + "[279871,287604], [295906,302319], [302575,309352], [318221,320436], [324492,326129], [326623,333708], "
        + "[340839,349361], [356638,361977], [368099,373667], [374773,377525], [378682,380033], [387254,396509], "
        + "[405096,411616], [421132,424029], [426427,435377], [442540,447244], [453501,459620], [462366,471360], "
        + "[473395,484316], [492462,502422], [503755,507454], [507551,510017], [511176,516561], [522063,525977], "
        + "[531770,537861], [540539,542996], [547329,557420], [560641,570186], [570284,578197], [583861,588606], "
        + "[591016,596724], [601714,610872], [614557,622940], [632723,634975], [636710,647340], [647937,657306], "
        + "[666519,671699], [673434,679252], [679505,687724], [695809,697606], [705905,710503], [719044,728326], "
        + "[735262,739796], [748048,753094], [762698,768074], [771762,781103], [786979,789938], [790140,794143], "
        + "[800910,806993], [807930,811850], [818716,827521], [828786,839104], [840596,850617], [851100,858980], "
        + "[863671,874042], [874432,880240], [889917,897380], [897599,904508], [910935,914564], [919538,927762], "
        + "[933690,942122], [951330,959747], [969266,978196], [984965,991648]]";
    String rangeSet3 = "[[3987,12147], [16890,26115], [34621,41095], [41476,44775], [50031,51695], [56539,60977], "
        + "[67558,76247], [83873,86817], [94900,102884], [111390,119073], [127792,138059], [145130,148633], "
        + "[155709,157847], [158118,161503], [164296,165881], [166123,169365], [178304,182866], [191004,193315], "
        + "[198648,199930], [204806,209054], [209177,213999], [214843,219858], [221497,223059], [228746,236624], "
        + "[241482,244679], [254433,255982], [257794,260287], [270207,277022], [278621,286999], [296719,303032], "
        + "[310590,318040], [323645,333283], [336166,341711], [347485,352255], [353348,358126], [362660,368061], "
        + "[376141,381147], [390178,393612], [399003,401626], [402609,412126], [419426,423852], [430009,432359], "
        + "[436647,442494], [446986,453904], [457694,461029], [466339,474088], [483026,486699], [495143,499556], "
        + "[506900,510220], [516325,521843], [523249,528070], [528549,532543], [533418,538998], [547895,549483], "
        + "[554460,555634], [562049,569098], [576463,584537], [588353,590300], [595284,600900], [609006,610452], "
        + "[618857,627533], [633186,637955], [642446,650849], [655326,662913], [663654,673388], [673914,678458], "
        + "[685951,690391], [699505,707103], [715822,718387], [725073,735513], [739306,741642], [750077,752683], "
        + "[759644,768461], [775885,778884], [783314,785772], [792568,802284], [806644,813017], [821962,828876], "
        + "[837176,847172], [854336,864364], [874180,881592], [888633,899508], [906913,907927], [908291,918558], "
        + "[927183,929930], [939548,949063], [951579,957887], [958917,960053], [968720,973220], [978731,989441]]";
    String expectedOutputRangeSet = "[[9148,10636], [18560,19300], [38008,41095], [41476,44775], [67558,68238], "
        + "[94900,96695], [111708,114232], [132587,134012], [134701,137518], [146406,146889], [147206,148633], "
        + "[155709,156680], [165855,165881], [166123,168693], [178304,179737], [180669,182866], [192538,193315], "
        + "[198648,199930], [207255,209054], [209177,211226], [218780,219152], [221497,223059], [230549,231541], "
        + "[233667,236624], [272168,272880], [282756,285555], [286030,286999], [296719,302319], [302575,303032], "
        + "[324492,326129], [326623,330498], [340839,341711], [356638,358126], [379830,380033], [390661,393612], "
        + "[409031,411616], [421748,423852], [446986,447244], [457694,459620], [469128,471360], [483038,484316], "
        + "[496477,499410], [506900,507364], [523249,523897], [524251,525977], [531770,532543], [533418,536822], "
        + "[554460,555367], [562049,565874], [576463,578197], [588353,588606], [596533,596724], [633582,634975], "
        + "[636710,637955], [642446,643323], [648357,650849], [655326,657306], [666519,671699], [673914,677174], "
        + "[685951,687223], [725073,728326], [735262,735513], [739306,739796], [750077,752683], [762698,768074], "
        + "[778521,778884], [800910,802284], [806644,806993], [807930,809167], [811769,811850], [824160,827521], "
        + "[828786,828876], [838445,839104], [840596,844533], [854336,858212], [863671,864364], [877243,880240], "
        + "[893193,895091], [911058,914564], [927183,927762], [939548,942122], [953197,956096], [969266,970314], "
        + "[984965,989441]]";

    List<List<IntPair>> sortedRangeSetList =
        Arrays.asList(constructRangeSet(rangeSet1), constructRangeSet(rangeSet2), constructRangeSet(rangeSet3));
    List<IntPair> expected = constructRangeSet(expectedOutputRangeSet);
    List<IntPair> actual = SortedRangeIntersection.intersectSortedRangeSets(sortedRangeSetList);
    Assert.assertEquals(actual, expected);
  }