我们把顶点分为凸顶点和凹顶点。显然每次操作要么连接两个凹顶点，要么连接一个凹顶点和一条边上的某个点。最终目的是删除所有凹顶点，因此只需要最大化连接两个凹顶点的线段数量。

纵向的线段是平凡的，横向的线段可以用单调栈处理，数量也只有 $O(n)$。选择的线段不能相交，因此问题转化为二分图最大独立集，也即二分图最大匹配。注意到每条横向线段都能匹配一个区间的纵向线段，因此从左到右扫，每次优先匹配右端点最小的即可。

时间复杂度 $O(n\log n)$。