排序、打包和重新映射索引值数组,以最小化重叠

位置:

概述:

我有这样的想法:

std::vector<SomeType> values;
std::vector<int> indexes;

struct Range{
    int firstElement;//first element to be used in indexes array
    int numElements;//number of element to be used from indexed array
    int minIndex;/*minimum index encountered between firstElement 
        and firstElements+numElements*/
    int maxIndex;/*maximum index encountered between firstElement 
        and firstElements+numElements*/
    Range()
        :firstElement(0), numElements(0), minIndex(0), maxIndex(0){
    }
}

std::vector<Range> ranges;

细节:

价值观 是某种类型的数组(好的,“向量”)(与哪种类型无关)。元素 价值观

索引 . 索引中的元素不是唯一的,一个值可能重复多个类型。和索引。size()>=values.size()。

范围 对应于来自 . firstElement是要从中使用的元素的索引 索引

((a.firstElement >= b.firstElement) && (a.firstElement < (b.firstElement+b.numElements)) == false

很明显,当我对你做手术的时候 价值观

现在,我需要重新安排 价值观 以最小化Range.maxIndex-Range.minIndex的方式。我不需要包装后的“最好”的结果,有“可能是最好的”或“好”的包装就足够了。

问题:
重新映射索引和重新计算范围很容易。问题是,我不知道如何对元素进行排序 价值观 ,因为在多个范围中可能会遇到相同的索引。

关于如何进行有什么想法吗?

限制:

不允许更改容器类型。容器应该像数组一样。没有地图,没有名单。 但在分拣过程中,你可以随意使用任何你想要的容器。 此外,没有升压或外部库-纯C++ + STL,我只需要一个算法。

其他信息:

没有为SomeType定义更大/更小的比较-只有相等/不相等。 但是不需要比较两个值,只需要比较索引。

算法的目标是确保

for (int i = 0; i < indexes.size; i++){ 
    print(values[indexes[i]]); //hypothetical print function
}

Range.maxIndex-Range.minIndex(排序后)尽可能小,以便通过合理的努力实现。 我不是在寻找一个“完美的”或“最佳的”解决方案,有一个“可能完美的”或“可能最佳的”解决方案就足够了。

附笔。 这是 家庭作业。