CF1285E Delete a Segment

There are $ n $ segments on a $ Ox $ axis $ [l_1, r_1] $ , $ [l_2, r_2] $ , ..., $ [l_n, r_n] $ . Segment $ [l, r] $ covers all points from $ l $ to $ r $ inclusive, so all $ x $ such that $ l \le x \le r $ . Segments can be placed arbitrarily — be inside each other, coincide and so on. Segments can degenerate into points, that is $ l_i=r_i $ is possible. Union of the set of segments is such a set of segments which covers exactly the same set of points as the original set. For example: - if $ n=3 $ and there are segments $ [3, 6] $ , $ [100, 100] $ , $ [5, 8] $ then their union is $ 2 $ segments: $ [3, 8] $ and $ [100, 100] $ ; - if $ n=5 $ and there are segments $ [1, 2] $ , $ [2, 3] $ , $ [4, 5] $ , $ [4, 6] $ , $ [6, 6] $ then their union is $ 2 $ segments: $ [1, 3] $ and $ [4, 6] $ . Obviously, union is a set of pairwise non-intersecting segments. You are asked to erase exactly one segment of the given $ n $ so that the number of segments in the union of the rest $ n-1 $ segments is maximum possible. For example, if $ n=4 $ and there are segments $ [1, 4] $ , $ [2, 3] $ , $ [3, 6] $ , $ [5, 7] $ , then: - erasing the first segment will lead to $ [2, 3] $ , $ [3, 6] $ , $ [5, 7] $ remaining, which have $ 1 $ segment in their union; - erasing the second segment will lead to $ [1, 4] $ , $ [3, 6] $ , $ [5, 7] $ remaining, which have $ 1 $ segment in their union; - erasing the third segment will lead to $ [1, 4] $ , $ [2, 3] $ , $ [5, 7] $ remaining, which have $ 2 $ segments in their union; - erasing the fourth segment will lead to $ [1, 4] $ , $ [2, 3] $ , $ [3, 6] $ remaining, which have $ 1 $ segment in their union. Thus, you are required to erase the third segment to get answer $ 2 $ . Write a program that will find the maximum number of segments in the union of $ n-1 $ segments if you erase any of the given $ n $ segments. Note that if there are multiple equal segments in the given set, then you can erase only one of them anyway. So the set after erasing will have exactly $ n-1 $ segments.

N/A

N/A