EEE 题,题解中说到一个典型的贪心问题,可是我不对,所以来问一下。
有一个长度为 nnn 的数轴和一些区间,数轴上有一些黑点,你要选最少的区间,满足每个黑点至少被一个区间包含
这是一个经典的贪心问题,我们从左往右考虑所有黑点,如果它还未被覆盖,就在所有覆盖它的区间中选出右端点最靠右的一个区间,可以 O(n)O(n)O(n) 贪心解决
我有个疑惑,在枚举黑点的时候怎么判断黑点被那些区间覆盖呀,还有就是怎么判断他是否被覆盖,对区间标号并打标记吗,还是怎么做,求大佬解答