GabWiki

Appearance

贪心 ​

区间合并 ​

将所有存在交集的区间合并

Java
static final int NEG_INF = (int) -2e9;

List<int[]> merge(List<int[]> segs) {
    segs.sort((a, b) -> a[0] - b[0]);
    List<int[]> res = new ArrayList<>();
    int st = NEG_INF, ed = NEG_INF;	
    for (int[] seg : segs) {
        if (ed < seg[0]) {
            if (st != NEG_INF) res.add(new int[]{st, ed});
            st = seg[0];
            ed = seg[1];
        } else ed = Math.max(ed, seg[1]);
    }
    if (st != NEG_INF) res.add(new int[]{st, ed});
    return res;
}
static final int NEG_INF = (int) -2e9;

List<int[]> merge(List<int[]> segs) {
    segs.sort((a, b) -> a[0] - b[0]);
    List<int[]> res = new ArrayList<>();
    int st = NEG_INF, ed = NEG_INF;	
    for (int[] seg : segs) {
        if (ed < seg[0]) {
            if (st != NEG_INF) res.add(new int[]{st, ed});
            st = seg[0];
            ed = seg[1];
        } else ed = Math.max(ed, seg[1]);
    }
    if (st != NEG_INF) res.add(new int[]{st, ed});
    return res;
}
C++
const int NEG_INF = -2e9;

void merge(vector<PII>& segs) {
    sort(segs.begin(), segs.end());
    vector<PII> res;
    int st = NEG_INF, ed = NEG_INF;
    for (const auto& seg : segs) {
        if (ed < seg.first) {
            if (st != NEG_INF) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        } else ed = max(ed, seg.second);
    }
    if (st != NEG_INF) res.push_back({st, ed});
    segs = res;
}
const int NEG_INF = -2e9;

void merge(vector<PII>& segs) {
    sort(segs.begin(), segs.end());
    vector<PII> res;
    int st = NEG_INF, ed = NEG_INF;
    for (const auto& seg : segs) {
        if (ed < seg.first) {
            if (st != NEG_INF) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        } else ed = max(ed, seg.second);
    }
    if (st != NEG_INF) res.push_back({st, ed});
    segs = res;
}