CF754D Fedor and coupons

我们所有的角色都有各自的爱好，Fedor 也不例外。他喜欢在邻近的超市购物。 超市中的商品拥有唯一的整数编号。并且，对于每一个整数，都有一个商品，其编号等于这个整数。Fedor 有 $n$ 张优惠券，第 $i$ 张优惠券可以用于编号在 $l_i$ 到 $r_i$（包含两端）的商品。今天，Fedor 想要带上恰好 $k$ 张优惠券。 Fedor 希望选择这 $k$ 张优惠券，使得存在尽可能多的商品 $x$，这 $k$ 张优惠券都能用于商品 $x$（即所有优惠券的区间重叠部分尽量大，具体见样例）。为了节省时间，Fedor 请你帮他选择这些优惠券。请帮助 Fedor！

第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 3 \cdot 10^{5}$），分别表示 Fedor 拥有的优惠券数量和他想选择的优惠券数量。 接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$-10^9 \leq l_i \leq r_i \leq 10^9$），表示第 $i$ 张优惠券可使用的商品编号区间。优惠券之间可以有重复。

第一行输出一个整数，表示可以同时使用所有所选优惠券购买商品的最大数量。如果所有选中的优惠券区间没有交集，则为 $0$。 第二行输出 $k$ 个不同的整数 $p_1,p_2,\ldots,p_k$（$1\leq p_i\leq n$），表示 Fedor 应该选择的优惠券的编号。 如果有多组方案，输出其中任意一种均可。

在第一个样例中，如果选择第 1 和第 2 张优惠券，则所有编号在 $[40,70]$ 区间内的商品都可以用两张优惠券购买，一共 $31$ 个商品。 在第二个样例中，任意两张优惠券没有交集，所以能同时使用两张优惠券购买的商品数量为 $0$。在这种情况下，Fedor 可以选择任意两张优惠券。 由 ChatGPT 5 翻译