重叠区间和最小值
Overlapping Intervals and Minimum Values
如何确定是否存在满足特定给定条件的一组值。标准采用区间和区间内的最小值的形式。
例如，给定条件：
Interval : Minimum value in that interval
{2, 2} : 5
{1, 4} : 1
{4, 4} : 4
能满足的一组数值是
{1, 5, 1, 4}
另一方面，给定条件：
Interval : Minimum value in that interval
{2, 3} : 1
{1, 4} : 2
{4, 4} : 4
不存在满足它们的这样一组值。
我想确定是否存在一组满足给定条件的值（即，如果存在一组满足条件的值，我只想找到一个 returns 为真的算法如果没有则为假）。
我知道如何使用 O(N^2) 的蛮力来做到这一点，但如果可能的话，我想实现 O(N lgN) 的解决方案。
我第一次尝试解决这个问题涉及合并重叠区间，然后检查合并区间的最低值，但我很快意识到这样做并不能保证得到正确的答案。
我的第二次尝试涉及线段树，即尝试为每个值分配值，如果您试图覆盖一个区间，那么这样的区间不存在。但是，这也很快被放弃，因为即使某些部分被覆盖，您仍然可以达到一组有效的值。
我的第三次尝试涉及区间树，试图找到两个区间之间的交点并检查是否可以创建一组有效的值。这看起来很有希望，但它是一个 O(N^2) 算法，因此也被放弃了。
谁能提供一些见解？
赋值的思路是正确的。您只需要按间隔的最小值（按递增顺序）对间隔进行排序。也就是说，解决方案如下所示：
构建一个线段树（所有节点的值为-infinity）。
按排序顺序处理所有区间。对于每个间隔，只需分配其值（无论之前有什么）。
运行 查询所有间隔以检查一切是否正确。
唯一不平凡的说法是：如果这个算法没有找到解决方案，那么就没有解决方案。我不会 post 正式证明，但这里有关键观察：
我们在按排序顺序处理时，必须给整个区间赋一个新值。
我们不会在其他任何地方分配一个新值（也就是说，我们不能意外地破坏另一个间隔的值）。
如何确定是否存在满足特定给定条件的一组值。标准采用区间和区间内的最小值的形式。
例如，给定条件：
Interval : Minimum value in that interval
{2, 2} : 5
{1, 4} : 1
{4, 4} : 4
能满足的一组数值是
{1, 5, 1, 4}
另一方面，给定条件：
Interval : Minimum value in that interval
{2, 3} : 1
{1, 4} : 2
{4, 4} : 4
不存在满足它们的这样一组值。
我想确定是否存在一组满足给定条件的值（即，如果存在一组满足条件的值，我只想找到一个 returns 为真的算法如果没有则为假）。
我知道如何使用 O(N^2) 的蛮力来做到这一点，但如果可能的话，我想实现 O(N lgN) 的解决方案。
我第一次尝试解决这个问题涉及合并重叠区间，然后检查合并区间的最低值，但我很快意识到这样做并不能保证得到正确的答案。
我的第二次尝试涉及线段树，即尝试为每个值分配值，如果您试图覆盖一个区间，那么这样的区间不存在。但是，这也很快被放弃，因为即使某些部分被覆盖，您仍然可以达到一组有效的值。
我的第三次尝试涉及区间树，试图找到两个区间之间的交点并检查是否可以创建一组有效的值。这看起来很有希望，但它是一个 O(N^2) 算法，因此也被放弃了。
谁能提供一些见解？
赋值的思路是正确的。您只需要按间隔的最小值（按递增顺序）对间隔进行排序。也就是说，解决方案如下所示：
构建一个线段树（所有节点的值为-infinity）。
按排序顺序处理所有区间。对于每个间隔，只需分配其值（无论之前有什么）。
运行 查询所有间隔以检查一切是否正确。
唯一不平凡的说法是：如果这个算法没有找到解决方案，那么就没有解决方案。我不会 post 正式证明，但这里有关键观察：
我们在按排序顺序处理时，必须给整个区间赋一个新值。
我们不会在其他任何地方分配一个新值（也就是说，我们不能意外地破坏另一个间隔的值）。