Overview

This problem asks you to select at most \(K\) intervals (reading plans) from \(M\) given intervals such that the total covered range (number of distinct book types read) is maximized.

Since intervals can overlap each other, a simple greedy approach does not work. However, by combining “removal of interval containment relationships”, “dynamic programming (DP)”, and “sliding window maximum”, we can solve it efficiently within the time limit.

---

Analysis

1. Removing Contained Intervals

First, if an interval \(A\) is completely contained within another interval \(B\) (\(L_B \leq L_A\) and \(R_A \leq R_B\)), there is no benefit in selecting interval \(A\). This is because selecting interval \(B\) instead of interval \(A\) uses the same \(1\) plan while covering a wider (or equal) range.

Therefore, we can safely exclude in advance any interval that is completely contained within another interval.

After removing containment relationships, if we sort the remaining intervals in ascending order of their left endpoints \(L_i\), the right endpoints \(R_i\) will also be strictly monotonically increasing. That is, for any two adjacent intervals \(i, i+1\), the following relationship holds: $\(L_i < L_{i+1} \quad \text{and} \quad R_i < R_{i+1}\)$

This ensures that the positional relationships of intervals are “neatly arranged from left to right,” making it easier to apply dynamic programming (DP).

2. Designing the Dynamic Programming (DP)

We focus on the fact that \(K\) is very small, at most \(10\). Let \(M'\) be the number of intervals after removing containment, and define the following DP:

• \(\text{dp}[i][j]\): the maximum covered length when the \(i\)-th interval is the last one selected and a total of \(j\) intervals have been selected so far

When choosing interval \(i\) as the next interval, let \(p\) (\(0 \le p < i\)) be the interval selected immediately before it. Depending on how interval \(p\) and interval \(i\) overlap, the newly added covered range falls into one of two patterns:

Pattern A: No overlap (\(R_p < L_i\))

Interval \(p\) and interval \(i\) are completely separated. The newly covered length is simply the length of interval \(i\) (\(R_i - L_i + 1\)). $\(\text{dp}[i][j] = \text{dp}[p][j-1] + (R_i - L_i + 1)\)$

Pattern B: Overlap exists (\(R_p \geq L_i\))

Since containment relationships have been removed, the positional relationship is \(L_p < L_i \leq R_p < R_i\). The overlapping portion is \([L_i, R_p]\), so the newly covered length is the right portion excluding the overlap (\(R_i - R_p\)). $\(\text{dp}[i][j] = \text{dp}[p][j-1] + (R_i - R_p)\)$

---

Algorithm

Speeding Up Transitions

If we naively try all transitions for every \(p < i\), the DP computation takes \(O(M^2 K)\), which is too slow for \(M = 10^5\). Therefore, we speed up the transitions.

Let \(\text{th}\) be the boundary index between Pattern A and Pattern B. This is the smallest \(p\) satisfying \(R_p \geq L_i\). Since \(L_i\) increases as \(i\) increases, this boundary \(\text{th}\) only moves to the right (monotonically increasing).

1. Range \(p < \text{th}\) (Pattern A: No overlap)

In this range, we just need to add \(R_i - L_i + 1\) to the maximum value of \(\text{dp}[p][j-1]\). Each time \(\text{th}\) advances to the right, we maintain and update the maximum of \(\text{dp}[p][j-1]\) that we have passed as max_A, allowing us to retrieve the maximum in \(O(1)\) per step.

2. Range \(\text{th} \leq p < i\) (Pattern B: Overlap exists)

In this range, we want to find the maximum of \(\text{dp}[p][j-1] - R_p + R_i\). Since \(R_i\) does not depend on \(p\), we just need to know the maximum of \(\text{dp}[p][j-1] - R_p\) in the range \(\text{th} \leq p < i\).

When \(i\) increases by \(1\), the left end \(\text{th}\) of this range (window) moves to the right, and the right end \(i-1\) also moves to the right. This has the form of a “Sliding Window”, and by using a sliding window maximum algorithm (Monotonic Queue) with a deque, we can manage and retrieve the maximum in \(O(1)\) per step.

Unifying Transition Formulas in Implementation

In the code, the computation is elegantly unified by transforming as follows: $\(\text{dp}[i][j] = \text{best} + (R_i - L_i + 1)\)$

• For Pattern A: \(\text{best} = \text{dp}[p][j-1]\)
• For Pattern B: \(\text{best} = \text{dp}[p][j-1] - R_p + L_i - 1\)

By defining best this way, we can update \(\text{dp}[i][j]\) using the same formula regardless of which pattern applies.

---

Complexity

• Time Complexity: \(O(M \log M + KM)\)

  • Sorting and removing containment takes \(O(M \log M)\).
  • In the DP computation, the outer loop runs \(K\) times and the inner loop runs \(M'\) times (\(M' \le M\)). Within the inner loop, element additions/removals from the deque and advancing the boundary \(\text{th}\) are amortized \(O(1)\) overall, so the total DP computation is \(O(KM)\).
  • Since \(M \le 10^5\) and \(K \le 10\), this comfortably fits within the time limit.

• Space Complexity: \(O(KM)\)

  • We use \(O(KM)\) memory to store the DP table \(\text{dp}[M'+1][K+1]\).

---

Implementation Notes

1. Removing containment relationships: Sort the intervals in ascending order of \(L_i\) and descending order of \(R_i\). Scanning in this order, if we maintain max_r as the maximum right endpoint seen so far, any interval with \(R_i \le \text{max\_r}\) is contained within another interval and can be easily excluded.

2. Deque management for sliding window maximum: The deque stores pairs of (index, value). When adding a new element, we remove all elements from the back of the deque that have values smaller than the new one, maintaining the values in the deque in descending (monotonically decreasing) order. This ensures that the front of the deque always holds the maximum value within the current window.

   Source Code

from collections import deque
import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])

    intervals = []
    idx = 3
    for _ in range(M):
        l = int(data[idx])
        r = int(data[idx + 1])
        intervals.append((l, r))
        idx += 2

    # 包含関係にある区間の除去
    # Lの昇順、Rの降順でソート
    intervals.sort(key=lambda x: (x[0], -x[1]))

    filtered = []
    max_r = 0
    for l, r in intervals:
        if r > max_r:
            filtered.append((l, r))
            max_r = r

    M_prime = len(filtered)
    K = min(K, M_prime)

    if K == 0:
        print(0)
        return

    # 1-based indexにするために先頭にダミーを挿入
    L = [0] * (M_prime + 1)
    R = [0] * (M_prime + 1)
    for i in range(M_prime):
        L[i + 1] = filtered[i][0]
        R[i + 1] = filtered[i][1]

    # dp[i][j] : i番目の区間を最後に選び、合計j個選んだときの最大カバー数
    INF = float("inf")
    dp = [[-INF] * (K + 1) for _ in range(M_prime + 1)]
    dp[0][0] = 0

    ans = 0

    for j in range(1, K + 1):
        max_A = dp[0][j - 1]
        th = 1
        deq = deque()

        for i in range(1, M_prime + 1):
            # 1. i-1 をスライド窓の右端として追加
            if i - 1 >= 1:
                val = dp[i - 1][j - 1] - R[i - 1]
                if val > -INF:
                    while deq and deq[-1][1] <= val:
                        deq.pop()
                    deq.append((i - 1, val))

            # 2. th を進める (R[th] < L[i] の間)
            while th < i and R[th] < L[i]:
                if dp[th][j - 1] > -INF:
                    max_A = max(max_A, dp[th][j - 1])
                if deq and deq[0][0] == th:
                    deq.popleft()
                th += 1

            # 3. dp[i][j] の計算
            best = -INF
            if max_A > -INF:
                best = max(best, max_A)
            if deq:
                best = max(best, deq[0][1] + L[i] - 1)

            if best > -INF:
                dp[i][j] = best + (R[i] - L[i] + 1)
                ans = max(ans, dp[i][j])

    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.