最简单的算法来划分多个（可能是）重叠范围

Question

假设我有一个范围向量，我想将它们划分为多个分区。请注意，这与std :: partition的功能不同，后者是查找单个分区点。我想知道是否为此使用了STL或boost（或其他）？

为了说明我的要求，让我们从范围向量开始：

using Index = int;

struct Range
{
   // Indexes are inclusive, meaning this specifies [lo, hi] not [lo, hi)
   Index lo;
   Index hi; // hi is always guaranteed to be greater than lo
};
std:vector<Range> ranges = { {0, 3}, 
                             {1, 5}, 
                             {2, 4} };

我想做的是有一个对范围进行分区的函数，以便最终得到这样的结果：

std::map<Index, int> my_map = partition(ranges); // <<<--- This is the function I'm seeking
                 ^
                 |
                 +-- This 'int' is the partition number

它生成的地图看起来像这样（鉴于上面的数据）：

my_map = { {0, 0},    // Lower bound of 0 for partition 0, which is [0, 1)
           {1, 1},    // Lower bound of 1 for partition 1, which is [1, 2)
           {2, 2},    // Lower bound of 2 for partition 2, which is [2, 4)
           {4, 3},    // Lower bound of 4 for partition 3, which is [4, 5)
           {5, 4}, }; // Lower bound of 5 for partition 4, which is [5, ...]

现在，当我想知道什么位于什么分区中时：

Partition which(Index i)
{
    auto it = my_map.upper_bound(i);
    if (it != my_map.end())
        return (--it)->second;
    return my_map.size() - 1;
}       

Answer 1

似乎boost :: icl可以解决问题...感谢@sascha