将每种花的开放时刻和凋谢时刻转换为事件,开放时刻视为出现事件(+1),凋谢时刻的下一个时刻视为消失事件(-1),用同一个数组存下来并按照时间排序,之后依次遍历维护当前同时观赏到的花的种类数,更新最大值并统计每个值的持续时刻数。最后输出最大值和最大值的出现时刻个数。
需要注意的是,在处理同一时间的事件时应该先处理消失事件再处理出现事件,不然会让最大值错误。
小明有一个花园,里面种了 n 种不同的花。每种花都会在某个整数时刻准时开放,并在之后的某个整数时刻凋谢。对于第 i 种花,它的开放时刻为 si,凋谢时刻为 ti,这意味着在 [si,ti] 这个闭区间内的任意整数时刻,小明都能观赏到该种花。
小明想要挑选一个整数时刻去花园,使得他能够同时观赏到的花的种类数最多。他想知道,这个最大的种类数是多少,以及有多少个不同的整数时刻能让他观赏到这么多种花。
约束:花的种类数 n 满足 1≤n≤100000,所有 si 和 ti 均为正整数,且对于每种花都有 1≤si≤ti≤105。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.