植树节

思路

题目在说什么？有 个志愿者，每人负责给编号 的树苗各浇一次水，问被浇水次数最多的树苗被浇了多少次。

这是经典的差分数组问题。对区间 全部加 1，等价于在差分数组上 ++ 和 --。所有操作做完后，对差分数组求前缀和就能还原每个位置的实际值，取最大值即可。

复杂度

  • 时间：，其中 是坐标上界（）
  • 空间：

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    const int MAXN = 1000002;
    vector<int> diff(MAXN + 1, 0);
    for(int i = 0; i < n; i++){
        int l, r;
        scanf("%d %d", &l, &r);
        diff[l]++;
        if(r + 1 <= MAXN) diff[r + 1]--;
    }
    int ans = 0, cur = 0;
    for(int i = 0; i <= MAXN; i++){
        cur += diff[i];
        ans = max(ans, cur);
    }
    printf("%d\n", ans);
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int MAXN = 1000002;
        int[] diff = new int[MAXN + 1];
        for (int i = 0; i < n; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            diff[l]++;
            if (r + 1 <= MAXN) diff[r + 1]--;
        }
        int ans = 0, cur = 0;
        for (int i = 0; i <= MAXN; i++) {
            cur += diff[i];
            ans = Math.max(ans, cur);
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    MAXN = 1000002
    diff = [0] * (MAXN + 2)
    for _ in range(n):
        l, r = map(int, input().split())
        diff[l] += 1
        if r + 1 <= MAXN:
            diff[r + 1] -= 1
    ans = 0
    cur = 0
    for i in range(MAXN + 1):
        cur += diff[i]
        if cur > ans:
            ans = cur
    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const MAXN = 1000002;
    const diff = new Int32Array(MAXN + 2);
    for (let i = 1; i <= n; i++) {
        const [l, r] = lines[i].split(' ').map(Number);
        diff[l]++;
        if (r + 1 <= MAXN) diff[r + 1]--;
    }
    let ans = 0, cur = 0;
    for (let i = 0; i <= MAXN; i++) {
        cur += diff[i];
        if (cur > ans) ans = cur;
    }
    console.log(ans);
});