思路

将流星持续时间转为流星出现时间和消失时间，用同一个数组存下来并按照时间排序，之后依次遍历维护最大值和每个值的出现次数即可。最后输出最大值和最大值的出现次数。

需要注意的是，在处理同一时间的事件时应该先处理消失的再处理出现的，不然会让最大值错误。

代码

C++

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,l,r) for(int i=(l);i<=(r);i++)
#define pii pair<int,int>
#define fi first
#define se second
const int N =1e5+10;

int st[N], ed[N];
int n;
pii a[N];
int m;
int ans[N], mx, now;

int main()
{
	cin >> n;
	f(i, 1, n) cin >> st[i];
	f(i, 1, n) cin >> ed[i];
	f(i, 1 ,n) {
		a[m++] = {st[i], 1};
		a[m++] = {ed[i]+1, -1};
	}
	sort(a, a+m);
	f(i, 0, m-1) {
		if(a[i].se == -1) {
			mx = max(mx, now);
			if(i != 0) ans[now] += a[i].fi - a[i-1].fi;
			now--;
		} else {
			now++;
		}
	}
	cout << mx << ' ' << ans[mx] << endl;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] l = new int[n];
        int[] r = new int[n];

        for (int i = 0; i < n; i++) {
            l[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            r[i] = scanner.nextInt();
        }

        TreeMap<Integer, Integer> mp = new TreeMap<>(); // 使用有序的哈希表进行离散化差分
        for (int i = 0; i < n; i++) {
            int a = l[i];
            int b = r[i];
            mp.put(a, mp.getOrDefault(a, 0) + 1);
            mp.put(b + 1, mp.getOrDefault(b + 1, 0) - 1);
        }

        TreeMap<Integer, Integer> cnts = new TreeMap<>(); // 统计观测到流星的频数
        int sum = 0;
        int pre = Arrays.stream(l).min().getAsInt();
        for (Map.Entry<Integer, Integer> entry : mp.entrySet()) {
            int u = entry.getKey();
            int v = entry.getValue();
            cnts.put(sum, cnts.getOrDefault(sum, 0) + (u - pre));
            sum += v;
            pre = u;
        }

        int maxCnt = 0;
        int maxNum = 0;
        for (Map.Entry<Integer, Integer> entry : cnts.entrySet()) {
            int u = entry.getKey();
            int v = entry.getValue();
            if (maxCnt < u) {
                maxCnt = u;
                maxNum = v;
            }
        }

        System.out.println(maxCnt + " " + maxNum);
    }
}

Python

n = int(input())
l = list(map(int, input().split()))
r = list(map(int, input().split()))

mp = {}  # 离散化差分
for i in range(n):
    a = l[i]
    b = r[i]
    mp[a] = mp.get(a, 0) + 1
    mp[b + 1] = mp.get(b + 1, 0) - 1

cnts = {}  # 统计观测到流星的频数
sum = 0
pre = min(l)
for u, v in sorted(mp.items()):
    cnts[sum] = cnts.get(sum, 0) + u - pre
    sum += v
    pre = u

maxCnt = 0
maxNum = 0
for u, v in cnts.items():
    if maxCnt < u:
        maxCnt = u
        maxNum = v

print(maxCnt, maxNum)

JS

let n = parseInt(readline())
let st = readline().split(' ').map(Number)
let ed = readline().split(' ').map(Number)
let a = [], m = 0
for(let i = 0 ; i < n ; i ++) {
    a[m++] = [st[i], 1]				//第一维a[i][0]存储时间，第二维a[i][1]存储出现或消失
    a[m++] = [ed[i]+1, -1]
}
a.sort((x, y) => (x[0] == y[0] ? x[1] - y[1] : x[0] - y[0]))		//先按照第一维排序，再按第二维排序
let ans = [], mx = 0, now = 0
for(let i = 0 ; i < m ; i ++) {
    if(a[i][1] == -1) {			//在每次流星即将消失的时候处理最大值，最大值时前一次一定是流星出现的事件，所以当前最大值的持续时间就是
        mx = Math.max(mx, now)																//a[i][0] - a[i-1][0]
        if(!ans[now]) {			//数组做字典用，如果字典中没有当前值，就初始化一下
            ans[now] = 0
        }
        ans[now] += a[i][0] - a[i-1][0]		//因为这里是消失事件，所以不可能是最早发生的，之前一定有一个出现事件比它早，所以a[i-1][0]不会越界
        now --
    } else {		//出现事件时不作处理，因为当前不可能是最大值
        now ++
    }
}
console.log(mx + " " + ans[mx])

题目内容

小美一直对天文学充满热情，他的房子位于一个相对较为偏远的地方，没有大城市那样的光污染，因此他拥有非常好的观测条件。他每晚都会抬头仰望星空，寻找流星的痕迹，记录下每颗流星出现和消失的时刻。

现在他收集了 $n$ 个流星在他所在观测地上空的出现时刻和消失时刻，对于一个流星，若其的出现时换为 $s$ ，消失时刻为 $t$ ，那么小美在时间段 $[s,t]$ 都能够观测到它。对于一个时刻， 观测地上空出现的流星数量越多，则小美认为该时刻越好。

小美希望能够选择一个最佳的时刻进行观测和摄影，使他能观测到最多数量的流星，现在小美想知道，在这个最佳时刻，他最多能观测到多少个流星以及一共有多少个最佳时刻可供他选择。

输入描述

第一行是一个正整数 $n$ ，表示流星的数量。

第二行是 $n$ 个用空格隔开的正整数，第 $i$个数 $s_i$ 表示第 $i$ 个流星的出现时间。

第三行是 $n$ 个用空格隔开的正整数，第 $i$ 个数 $t_i$ 表示第 $i$ 个流星的消失时间。

$1\le n\le 100000, 1\le s_i\le t_i\le 10^5$

原题面是1e9,思考如何做~

输出描述

输出一行用空格隔开的两个数 $x$ 和 $y$ ，其中 $x$ 小美能观测到的最多流星数， $y$ 表示可供他选择的最佳时刻数量。

样例

输入

3
2 1 5
6 3 7

输出

2 4

样例解释

在 $7$ 个时刻中，时刻 $2$ 、 $2$ 、 $5$ 、 $6$ 可以观测到 $2$ 个流星，其他时刻只能观测到 $1$ 个流星，所以最多能观测到的流星数量为 $2$ ，最佳时刻的数是 $4$ 。