Skip to content

2580. Count Ways to Group Overlapping Ranges 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int countWays(vector<vector<int>>& ranges) {
    constexpr int kMod = 1'000'000'007;
    int ans = 1;
    int prevEnd = -1;

    ranges::sort(ranges);

    for (const vector<int>& range : ranges) {
      const int start = range[0];
      const int end = range[1];
      if (start > prevEnd)
        ans = ans * 2 % kMod;
      prevEnd = max(prevEnd, end);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int countWays(int[][] ranges) {
    final int kMod = 1_000_000_007;
    int ans = 1;
    int prevEnd = -1;

    Arrays.sort(ranges, (a, b) -> a[0] - b[0]);

    for (int[] range : ranges) {
      final int start = range[0];
      final int end = range[1];
      if (start > prevEnd)
        ans = ans * 2 % kMod;
      prevEnd = Math.max(prevEnd, end);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def countWays(self, ranges: List[List[int]]) -> int:
    kMod = 1_000_000_007
    ans = 1
    prevEnd = -1

    for start, end in sorted(ranges):
      if start > prevEnd:
        ans = ans * 2 % kMod
      prevEnd = max(prevEnd, end)

    return ans