Давайте посмотрим на третью задачу из двухнедельного конкурса Leetcode 99. Решения различных задач из других конкурсов вы можете найти здесь.

Подсчет способов группировки перекрывающихся диапазонов

Вам дан двумерный массив целых чисел ranges, где ranges[i] = [starti, endi] означает, что все целые числа от starti до endi (оба включительно) содержатся в диапазоне ith.

Вам нужно разбить ranges на две (возможно, пустые) группы таким образом, чтобы:

Каждый диапазон принадлежит ровно одной группе.

Любые два перекрывающихся диапазона должны принадлежать одной и той же группе.

Два диапазона называются перекрывающимися, если существует хотя бы одно целое число, которое присутствует в обоих диапазонах.

Например, [1, 3] и [2, 5] перекрываются, потому что 2 и 3 встречаются в обоих диапазонах.

Возвращает общее количество способов разделения ranges на две группы. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Решение

Совершенно очевидно, что эту проблему можно разделить на две отдельные проблемы:

  1. Найдите количество непересекающихся диапазонов
  2. Найдите количество возможных разбиений для известного количества непересекающихся диапазонов.

Давайте рассмотрим эти проблемы одну за другой.

Найти количество непересекающихся диапазонов

Отсортируем массив диапазонов по их началу и рассмотрим интервалы по порядку. Сравним следующий интервал с ранее рассмотренным. Мы можем столкнуться с двумя ситуациями:

  1. начало[следующий] ≤ конец[предыдущий]

Следующийинтервал перекрывает предыдущий — нам нужно объединить интервалы. Как мы можем объединить перекрывающиеся интервалы? Возможны два случая:

1.1 конец[следующий] ≥ конец[предыдущий]

1.2 конец[следующий]‹конец[предыдущий]

Чтобы получить объединенные границы интервалов, мы можем использовать следующую формулу: начало[объединено]=начало[предыдущий]интервалы отсортированы таким образом, что начало[предыдущее] всегда ниже, конец[объединено] = max( конец[следующий], конец[предыдущий]) — получаем наибольший из двух концов для нового интервала. После объединения мы начинаем сравнивать следующий интервал с объединенным.

2. начало[следующий] › конец[предыдущий]следующий интервал не перекрывает предыдущий, мы просто начинаем использовать следующий интервал для сравнения со следующими интервалами.

function mergeIntervals(){
  ranges.sort((r1, r2) => r1[0] - r2[0])
    
  let res = [ranges[0]]
  for(let next of ranges){
      let prev = res[res.length-1]
      // Compare end of previous with start of next interval
      if(prev[1] >= next[0]){
          // Intervals overlap
          prev[1] = Math.max(prev[1], next[1])
      }else{
          // Intervals not overlap
          res.push(next)
      }
  }

  return res
}

Рассчитать количество способов разделения диапазонов

Мы подсчитали количество непересекающихся интервалов, но теперь нам нужно подсчитать количество возможных разбиений. На самом деле нам нужно вычислить количество возможных подпоследовательностей для объединенного массива. Количество возможных подпоследовательностей для массива длины N будет равно 2^N.

Код

var countWays = function(ranges) {
    let mod = Math.pow(10, 9) + 7
    ranges.sort((r1, r2) => r1[0] - r2[0])
    
    let res = [ranges[0]]
    for(let next of ranges){
        let prev = res[res.length-1]
        // Compare end of previous with start of next interval
        if(prev[1] >= next[0]){
            // Intervals overlap
            prev[1] = Math.max(prev[1], next[1])
        }else{
            // Intervals not overlap
            res.push(next)
        }
    }
    
    let n = res.length
    
    let sum = 1
    // Calculate 2^N mod (10^9 + 7)
    for(let i = 1; i <= n; i++){
        sum = (sum * 2) % mod
    }
    
    return sum
};

Сложность

Временная сложность:O(N*Log(N))

Пространственная сложность:O(N)

P.S.

Вот мое решение на Leetcode.