算法：给定一个区间，在集合中找出所有与之相交的区间。

Cocos2d-x
#1

给定区间a
区间集合S，含有1000个区间。这些区间可能相交，或相连，或包含等。
所有区间都是闭区间。区间，大小随机，范围随机。
找出S中所有与a相交的区间，只交一个点也算。

可以对S先处理，如排序啊或做一个数据结构什么的。但要求在查找时不会遍历S中的所有区间。

有什么思路吗？或用什么数据结构？:726:

#2

感觉算法教材上有类似的问题，是属于哪一类的？忘了

#3

线段树应该可以。查找的时间复杂度是O(logN)，占用空间跟区间的上限有关，而且支持动态插入新区间。如果区间的数值比较大，例如，需要用一个叫"离散化"的技巧压缩空间。现在好久没碰算法了，我只是说一个可能行的思路。。

#4

刚才试着写了下，大概是这样的，应该还有待优化。

#include 
#include 
#include 

using namespace std;

struct tree_node {
    int left;
    int right;
    vector number;
};

const int max_size = 1000;
struct tree_node tree;

void build_tree(int left, int right, int step) {
    tree.left = left;
    tree.right = right;
    if(left < right) {
        int mid = (left + right) / 2;
        build_tree(left, mid, step<<1);
        build_tree(mid+1, right, step<<1|1);
    }
}

void insert_tree(int left, int right, int number, int step) {
    tree.number.push_back(number);
    if(tree.left == tree.right) {
        return;
    }
    int mid = (tree.left + tree.right) / 2;
    if(right <= mid) {
        insert_tree(left, right, number, step< mid) {
        insert_tree(left, right, number, step<<1|1);
    }
    else {
        insert_tree(left, mid, number, step<<1);
        insert_tree(mid+1, right, number, step<<1|1);
    }
}

void query_tree(set& answer, int left, int right, int step) {
    if(tree.left == left && tree.right == right) {
        for(auto it = tree.number.begin(); it != tree.number.end(); it++) {
            answer.insert(*it);
        }
        return;
    }
    int mid = (tree.left + tree.right) / 2;
    if(right <= mid) {
        query_tree(answer, left, right, step< mid) {
        query_tree(answer, left, right, step<<1|1);
    }
    else {
        query_tree(answer, left, mid, step<<1);
        query_tree(answer, mid+1, right, step<<1|1);
    }
}

int main() {

    int region] = {
        {3, 600},
        {2, 40},
        {4, 700},
        {1, 70},
        {1, 900}
    };

    build_tree(1, max_size, 1);

    for(int i = 0; i < 5; i++) {
        insert_tree(region*, region*, i, 1);
    }

    set answer;

    answer.clear();
    query_tree(answer, 1, 100, 1);
    for(auto it = answer.begin(); it != answer.end(); it++) {
        cout << *it << endl;
    }

    return 0;
}



```



**
#5

论坛有点乱码，把"i"的方括号显示成尖括号了.

#6

代码都给出了，动作真快。随便测试几下，结果正确。感谢哈。:867:

#7

去翻了下算法导论interval tree.还是有区别的。
3楼这个算法lgN中N的大小是区间的长度。。。并不是集合S中区间数量的大小。

如果S中的区间数量是1000。而区间的总范围是. 就差别很大。
发现1楼这种情况就是interval tree了哈。

如果区间范围比较小，S中段又多的话。3楼这种更高效。
interval tree比较复杂，找一个的话方便，找出所有据说要o(max(n,klogn))

#8

区间范围大的话，可以离散化，思路就是用小的数代替大的数。例如原区间是、，就用2代替100，用3代替100000，用4代替200000。这样既不会有歧义，而且节省了内存和查找时间。未离散化的线段树需要4倍区间大小的内存。:2:
如果区间范围小，那就没关系了，log(2^31) = 31而已。哈哈。

#9

3楼的代码应该不是太好，没有用到线段树的lazy思想，你可以压力测试一下，我也不确定能消耗多少时间。

#10

看了下wiki，可以直接用线段端点来建红黑树成为线段树，这样所用空间是N*lgN, 这里的N是线段数，不是区间大小。 红黑树有点麻烦，先放放了:764: