Feed Cats (Codeforces 1932F)
Tags: DP, sortings

There is a fun game where you need to feed cats that come and go. The level of the game consists of $$$n$$$ steps. There are $$$m$$$ cats; the cat $$$i$$$ is present in steps from $$$l_i$$$ to $$$r_i$$$, inclusive. In each step, you can feed all the cats that are currently present or do nothing. If you feed the same cat more than once, it will overeat, and you will immediately lose the game. Your goal is to feed as many cats as possible without causing any cat to overeat. Find the maximum number of cats you can feed.Formally, you need to select several integer points from the segment from $$$1$$$ to $$$n$$$ in such a way that among given segments, none covers two or more of the selected points, and as many segments as possible cover one of the selected points.

Input: The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then the descriptions of the test cases follow.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m\le 2\cdot 10^5$$$). The $$$i$$$-th of the next $$$m$$$ lines contains a pair of integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).The sum of $$$n$$$ for all tests does not exceed $$$10^6$$$, the sum of $$$m$$$ for all tests does not exceed $$$2\cdot 10^5$$$.

Output: For each test case, print a single integer, the maximum number of cats you can feed.

Note: In the first example, one of the ways to feed five cats is to feed at steps $$$4$$$ and $$$11$$$. At step $$$4$$$, cats $$$1$$$, $$$2$$$, and $$$3$$$ will be fed. At step $$$11$$$, cats $$$5$$$ and $$$6$$$ will be fed.

Sample Inputs:
3
15 6
2 10
3 5
2 4
7 7
8 12
11 11
1000 1
1 1000
5 10
1 2
3 4
3 4
3 4
3 4
1 1
1 2
3 3
3 4
3 4

Sample Outputs:
5
1
10

Solution (Python):
import sys
input = sys.stdin.readline
import heapq

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, m) = readInts()
    cnt = [0] * (n + 2)
    ma = [0] * (n + 2)
    for _ in range(m):
        (l, r) = readInts()
        cnt[l] += 1
        cnt[r + 1] -= 1
        ma[l] = max(ma[l], r)
    for i in range(1, n + 1):
        cnt[i] += cnt[i - 1]
        ma[i] = max(ma[i], ma[i - 1])
    dp = [0] * (n + 2)
    for i in range(n, -1, -1):
        dp[i] = max(dp[i + 1], cnt[i] + dp[ma[i] + 1]) if cnt[i] else dp[i + 1]
    return dp[0]
for _ in range(int(input())):
    print(solve())

Solution (Python):
from typing import List
from collections import defaultdict, deque
from itertools import accumulate
from collections import Counter
import heapq
import sys
from math import comb, perm
import random
import os

def input():
    return sys.stdin.readline().strip()
script_directory = os.path.dirname(os.path.abspath(__file__))
os.chdir(script_directory)
if os.path.exists('input.txt'):
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')

def readNum():
    return int(input())

def readArr():
    return list(map(int, input().split()))

def readMulti():
    return map(int, input().split())

def readStr():
    return input()

def readStrArr():
    return list(input().split())

def main():
    (n, m) = readMulti()
    njump = [-1] * (n + 1)
    diff = [0] * (n + 2)
    dp = [0] * (n + 2)
    for _2 in range(m):
        (l, r) = readMulti()
        njump[l] = max(r, njump[l])
        diff[l] += 1
        diff[r + 1] -= 1
    for i in range(1, n + 1):
        njump[i] = max(njump[i], njump[i - 1])
    catsArr = [0]
    for cur in diff[1:]:
        catsArr.append(catsArr[-1] + cur)
    for i in range(n, 0, -1):
        j = njump[i]
        if j == -1:
            dp[i] = dp[i + 1]
        else:
            dp[i] = max(dp[i + 1], catsArr[i] + dp[njump[i] + 1])
    print(dp[1])
    return
numberOfTesting = readNum()
for _ in range(numberOfTesting):
    main()

Solution (Python):
outputTogether = 0
from typing import List
from collections import defaultdict, deque
from itertools import accumulate
from collections import Counter
import heapq
import sys
from math import comb, perm
import random
import os
input = lambda : sys.stdin.readline().strip()
if outputTogether:
    from io import BytesIO, IOBase

    class FastIO(IOBase):
        newlines = 0

        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = 'x' in file.mode or 'r' not in file.mode
            self.write = self.buffer.write if self.writable else None

        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
            self.newlines = 0
            return self.buffer.read()

        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b'\n') + (not b)
                ptr = self.buffer.tell()
                (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
            self.newlines -= 1
            return self.buffer.readline()

        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                (self.buffer.truncate(0), self.buffer.seek(0))

    class IOWrapper(IOBase):

        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode('ascii'))
            self.read = lambda : self.buffer.read().decode('ascii')
            self.readline = lambda : self.buffer.readline().decode('ascii')
    sys.stdout = IOWrapper(sys.stdout)
script_directory = os.path.dirname(os.path.abspath(__file__))
os.chdir(script_directory)
if os.path.exists('input.txt'):
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')

def readNum():
    return int(input())

def readArr():
    return list(map(int, input().split()))

def readMulti():
    return map(int, input().split())

def readStr():
    return input()

def readStrArr():
    return list(input().split())

def main():
    (n, m) = readMulti()
    njump = [-1] * (n + 1)
    diff = [0] * (n + 2)
    dp = [0] * (n + 2)
    for _2 in range(m):
        (l, r) = readMulti()
        njump[l] = max(r, njump[l])
        diff[l] += 1
        diff[r + 1] -= 1
    for i in range(1, n + 1):
        njump[i] = max(njump[i], njump[i - 1])
    catsArr = [0]
    for cur in diff[1:]:
        catsArr.append(catsArr[-1] + cur)
    for i in range(n, 0, -1):
        j = njump[i]
        if j == -1:
            dp[i] = dp[i + 1]
        else:
            dp[i] = max(dp[i + 1], catsArr[i] + dp[njump[i] + 1])
    print(dp[1])
    return
numberOfTesting = readNum()
for _ in range(numberOfTesting):
    main()