[itint5]区间相交 - 阿牧遥 - 博客园

[itint5]区间相交 - 阿牧遥 - 博客园
要记录原来的索引，所以用了额外的空间，新生成一个结构。如果要省空间，可以用指针来排序，最后拿指针减去索引0的位置就是index，见：http://www.itint5.com/discuss/172/%E4%B8%BA%E5%95%A5%E6%88%91%E8%BF%99%E9%A2%98%E5%9C%A8%E5%A4%A7%E6%95%B0%E6%8D%AE%E6%97%B6%E4%BC%9Asegmentation-fault
这里没有用指针，也有很多错误，足可见面试时不要自取其辱，寻找合理的方法即可。
一要注意，sort和comp函数，因为是高级的，所以返回bool，并且参数是const引用。二要注意，排完序后，并不是前一个和后一个比较就行了，要记录之前的end最大的那个。

struct IntervalPair {

    int start;

    int end;

    int idx;

};

 

bool comp(const IntervalPair &pa, const IntervalPair &pb) {

    if (pa.start != pb.start) {

        return pa.start < pb.start;

    } else {

        return pb.end < pb.end;

    }

}

 

void intersected(vector<Interval> &intervals, vector<bool> &isIntersected) {

    int size = intervals.size();

    if (size <= 1) return;

    vector<IntervalPair> vec(size);

    for (int i = 0; i < size; i++) {

        vec[i].start = intervals[i].start;

        vec[i].end = intervals[i].end;

        vec[i].idx = i;

    }

    sort(vec.begin(), vec.end(), comp);

    int max_end = vec[0].end;

    int max_end_idx = 0;

    for (int i = 0; i < size - 1; i++) {

        if (vec[i].end > max_end) {

            max_end = vec[i].end;

            max_end_idx = i;

        }

        if (max_end >= vec[i+1].start) {

            isIntersected[vec[max_end_idx].idx] = true;

            isIntersected[vec[i+1].idx] = true;

        }

    }

}

https://github.com/AnnieKim/ITint5/blob/master/014_%E5%8C%BA%E9%97%B4%E7%9B%B8%E4%BA%A4.cpp
 链接: http://www.itint5.com/oj/#14
 问题:
 有n个左右端点都为整数的区间，判断每个区间是否有与其它某个区间相交（区间端点重合也算相交）。
 Solution: 按照区间左端点进行排序，并按照从小到大顺序进行遍历。
           遍历过程中记录目前为止的最大右端点。
           判断区间是否相交，就只需判断当前区间的左端点是否小于或等于最大右端点。
struct Interval {
    int start; //区间左端点
    int end;   //区间右端点
};
*/

bool compare(pair<int, Interval> a, pair<int, Interval> b) {
    return a.second.start < b.second.start;
}

// intervals包含n个区间
// 结果存放到isIntersected中(已分配空间,不需要push_back)
// isIntersected[i]表示第i个区间是否与其它区间相交
void intersected(vector<Interval> &intervals, vector<bool> &isIntersected) {
    int N = intervals.size();
    if (N == 0) return;

    pair<int, Interval> itvl[N];
    for (int i = 0; i < N; ++i)
        itvl[i] = make_pair(i, intervals[i]);
    sort(itvl, itvl + N, compare);
   
    int max_end = 0;
    isIntersected[itvl[0].first] = false;
    for (int i = 1; i < N; ++i)
    {
        if (itvl[i].second.start <= itvl[max_end].second.end)
            isIntersected[itvl[i].first] = isIntersected[itvl[max_end].first] = true;
        if (itvl[max_end].second.end < itvl[i].second.end)
            max_end = i;
    }
}

https://github.com/zdzapple/itint5/blob/master/%E5%8C%BA%E9%97%B4%E7%9B%B8%E4%BA%A4.cpp
struct Interval {
    int start;   //区间左端点
    int end;   //区间右端点
};
*/
struct IntervalID
{
Interval interval;
int id;
};
// compare 不能只比较一边
bool compare1(const IntervalID &first, const IntervalID &second)
{
if (first.interval.end < second.interval.end)
return true;
return false;
}

bool compare(const IntervalID &first, const IntervalID &second)
{
if (first.interval.start != second.interval.start)
return first.interval.start < second.interval.start;
else return first.interval.end < second.interval.end;
}

// intervals包含n个区间
// 结果存放到isIntersected中(已分配空间,不需要push_back)
// isIntersected[i]表示第i个区间是否与其它区间相交
void intersected(vector<Interval> &intervals, vector<bool> &isIntersected)
{
int n = intervals.size();
if (intervals.empty())
return;
vector<IntervalID> intervalsWithID;
for (int i = 0; i < n; ++ i)
{
IntervalID intervalid;
intervalid.interval = intervals[i];
intervalid.id = i;
intervalsWithID.push_back(intervalid);
isIntersected[i] = false;
}
sort(intervalsWithID.begin(), intervalsWithID.end(), compare);
// 使用一个线段表示当前相交的线段总长
// 如果只比较一端的话，会有特殊情况无法排除
int maxEnd = intervalsWithID[0].interval.end;
int maxEndID = intervalsWithID[0].id; // 不是0！！
for (int i = 1; i < n; ++ i)
{
IntervalID intervalid = intervalsWithID[i];
if (intervalid.interval.start <= maxEnd) {
isIntersected[intervalid.id] = true;
isIntersected[maxEndID] = true;
maxEnd = max(intervalid.interval.end, maxEnd);
} else {
maxEndID = intervalid.id;
maxEnd = intervalid.interval.end;
}

}
}

Read full article from [itint5]区间相交 - 阿牧遥 - 博客园