# 算法模板—区间合并(Algorithm template – interval merging)-其他

## 算法模板—区间合并(Algorithm template – interval merging)

### my’code

class CountIntervals {
public:
typedef pair<int,int> PII;
set<PII> heap;
int ans=0;
CountIntervals() {

}

void add(int left, int right) {
int l=left,r=right;
auto it  = heap.lower_bound(PII(left-1,-2e9));
while(it!=heap.end()){
if(it->second>right+1)break;
l=min(l,it->second);
r=max(r,it->first);
ans-=it->first-it->second+1;
heap.erase(it++);
}
ans+=r-l+1;
heap.insert(PII(r,l));

}

int count() {
return ans;
}
};

/**
* Your CountIntervals object will be instantiated and called as such:
* CountIntervals* obj = new CountIntervals();
* int param_2 = obj->count();
*/

### 模板

class section {
public:
using pii = pair<int, int>;
set<pii> s;//反向存储，{right, left} == [left, right)
uint64_t count;
section(uint64_t n = 0) :count(n) {}

int insert(const pii& x) { // 区间 [left, right)
if (x.first >= x.second)return false;
uint64_t before = count;
for (auto p = s.lower_bound({ x.first, INT_MIN }); p != s.end() && p->second <= x.second; ) {
count -= p->first - p->second;
p = s.erase(p);
}
return count > before;
}
};

class CountIntervals {
public:
section s;
CountIntervals() {

}

void add(int left, int right) {
s.insert({left, right + 1});
}

int count() {
return s.count;
}
};

————————

### Interval merging

Number of integers in statistical interval

Number of integers in statistical interval

### analysis

< strong > using the set reverse storage interval is conducive to passing through the lower_ Bound() find the interval whose right end point is greater than or equal to left-1 < / strong >
< strong > continuously delete the intersecting intervals by L and R merging intervals < / strong >

< strong > using the set reverse storage interval is conducive to passing through the lower_ Bound() find the interval whose right end point is greater than or equal to left-1 < / strong >
< strong > continuously delete the intersecting intervals by L and R merging intervals < / strong >

### my’code

class CountIntervals {
public:
typedef pair<int,int> PII;
set<PII> heap;
int ans=0;
CountIntervals() {

}

void add(int left, int right) {
int l=left,r=right;
auto it  = heap.lower_bound(PII(left-1,-2e9));
while(it!=heap.end()){
if(it->second>right+1)break;
l=min(l,it->second);
r=max(r,it->first);
ans-=it->first-it->second+1;
heap.erase(it++);
}
ans+=r-l+1;
heap.insert(PII(r,l));

}

int count() {
return ans;
}
};

/**
* Your CountIntervals object will be instantiated and called as such:
* CountIntervals* obj = new CountIntervals();
* int param_2 = obj->count();
*/

### Template

class section {
public:
using pii = pair<int, int>;
set<pii> s;//反向存储，{right, left} == [left, right)
uint64_t count;
section(uint64_t n = 0) :count(n) {}

int insert(const pii& x) { // 区间 [left, right)
if (x.first >= x.second)return false;
uint64_t before = count;
for (auto p = s.lower_bound({ x.first, INT_MIN }); p != s.end() && p->second <= x.second; ) {
count -= p->first - p->second;
p = s.erase(p);
}
return count > before;
}
};

class CountIntervals {
public:
section s;
CountIntervals() {

}

void add(int left, int right) {
s.insert({left, right + 1});
}

int count() {
return s.count;
}
};