题解

思路

把区间尽量向两端延伸不会使目标变差，因此可令每个左端点形如 $x_i+1$，每个右端点形如 $x_{i+1}-1$，并补上 $x_0=-\infty,x_{N+1}=+\infty,y_0=y_{N+1}=0$。

做法

记 $c_i=y_{i+1}-y_i$：若 $c_i>0$，就在 $x_i+1$ 处加入 $c_i$ 个左端点；若 $c_i<0$，就在 $x_{i+1}-1$ 处加入 $-c_i$ 个右端点。按坐标分别排序后，将第 $k$ 个左端点与第 $k$ 个右端点配对是最优的，因为任何逆序配对都可以交换而不减小最短区间长度；额外同时加入一个左、右端点也不可能改善答案，所以这组最少端点已经给出最优解。

端点重数可能达到 $10^9$，不能逐个展开。按下标顺序记录值与重数形成两个压缩序列，再用双指针每次消去当前两块重数的较小值；若两端均有限，就用右端点减左端点更新最小值。若所有配对都含无穷端点，则区间长度可以无限增大，答案为 $-1$。

复杂度

每个压缩块只被访问一次，时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。