使用[start, end)來表示一個區間，通常會包含start，但是不包含end。

x >= start && x < end;

可以使用vector<int>或是使用pair<int, int>來表示start和end。

vector<int> p = {start, end};
pair<int, int> q = make_pair(start, end);
// 多個區間
vector<vector<int>> intervals;
vector<pair<int, int>> intervals;

## Tips
### 檢查interval是否重疊
#### Method 1 : 檢查兩個interval的start和end

max(p.start, q.start);
min(p.end, q.end);

case 1. P和Q不重疊，Q在P後面

case 2. P和Q重疊，Q比較後面

case 3. P和Q重疊，Q比較前面

case 4. P和Q不重疊，Q在P前面

如果interval範圍的是 ==[start, end)==，沒包括end則:
當max(p.start, q.start) < min(p.end, q.end)時會發生overlap.

if(max(p.start, p.start) < min(p.end, q.end)) {
    // overlap occure    
}

如果interval範圍是 ==[start, end]== ，有包括end則:
當max(p.start, q.start) <= min(p.end, q.end)時會發生overlap。

if(max(p.start, q.start) <= min(p.end, q.end)) {
    // overlap occure    
}

#### Method 2: 檢查前後的關係

如果是 ==[start, end)== 的情況
有兩種情況會出現overlap。
1. curr.start < prev.end
2. curr.end > next.start

重點是使用curr.start去和end比較，使用curr.end和start做比較。

如果是 ==[start, end]== 的情況
則有兩種情況會出現overlap。
1. curr.start <= prev.end
2. curr.end >= next.start

### 把interval放進set或是map中
因為是使用ordered set或是ordered map，interval在這些container中會排序。

當放入set中
+ 會先依第一個數排列
+ 再依第二個數排列

因為是set，所以只能存不重複的pair或是vector。

set<pair<int, int>> s;
s.add(make_pair(2, 3));
s.add(make_pair(2, 1));
s.add(make_pair(3, 2));
// in container
// (2, 1), (2, 3), (3, 2)    

如果是放入map中，可把start當成key，end當成value。因為key不可以重複，所以只能用在key沒有重複的情況。

map<int, int> m;
m[4] = 2;
m[2] = 3;
// in container
// (2, 3), (4, 2)

### 使用sort來排序
除了使用set或是map來排序之外，也可以使用sort來排序。如果不使用compare fun結果和set的結果一樣。

1. 會先針對第一個element遞增排序。
2. 如果第一個element一樣，則會針對第二個element做遞增排序。

vector<vector<int>> intervals; // 使用vector
vector<pair<int, int>> intervals; // 使用pair    
sort(intervals.begin(), intervals.end());
// before (2, 1), (1, 5), (1, 3), (1, 2), (0, 4), 
// after  (0, 4), (1, 2), (1, 3), (1, 5), (2, 1)

另外也可以自訂compare func來達到自訂的排序效果。
例如可以依照end的順序來排序，如果end一樣則照length排序。

sort(intervals.begin(), intervals.end(), [&](vector<int>& a, vector<int>& b){
    if(a[1] < b[1]) return true;
    else if(a[1] == b[1]) return (a[1] - a[0]) > (b[1] - b[0]);
    else return false;
});

### binary search interval
放入ordered set或是使用過sort()來排序後，另一個好處是可以用binary search來找interval。

set<pair<int, int>> s;
vector<vector<int>> intervals;
// 尋找大於等於s的interval
// 先比較第一個element，如果一樣在比較第二個element
s.lower_bound({s, e}); 
auto it = lower_bound(intervals.begin(), intervals.end());
    
// for example : (2,3)(2,5)(3,1) in set
auto it = s.lower_bound({2, 3}); // it指向(2, 3)
it = s.lower_bound({2, 4}); // it指向(2, 5)
it = s.lower_bound({2, 6}); // it指向(3, 1)

#### [729. My Calendar I](https://leetcode.com/problems/my-calendar-i/)
設計一個系統可以註冊event，其中event有start和end。如果event重疊就返回false。

> 1. 使用order set來儲存events
> 2. 使用lower_bound找出大於等於的interval，
> 3. 使用前後的interval來判斷是否重疊。

class MyCalendar {
    set<pair<int, int>> books; // ordered set, <start, end>
public:
    MyCalendar() {
        
    } 
    bool book(int s, int e) {
        auto next = books.lower_bound({s, e});
        if (next != books.end() && next->first < e) return false;
        if (next != books.begin() && s < prev(next)->second) return false; 
        books.insert({ s, e });
        return true;
    }
};

### 計算重疊區間個數 method1
1. 先使用sort根據end遞增排序

vector<vector<int>> intervals;
sort(intervals.begin(), intervals.end(), [&](vector<int>& a, vector<int>& b){
    return a[1] < b[1];
});

2. 計算和curr重疊的區間
因為是根據end排序，所以只能只cur之後的做比較。
如果cur不是在第一個，哪就要先找出cur在哪，然後從後面iterator。

enum st{start, end};
vector<vector<int>> intervals;
int cur = 0, ans = 0;
for(int i = 1; i < intervals.size(); ++i) {
    if(intervals[cur][end] >= intervals[i][start])
        ans++;
}

==因為使用intervals[cur][end] >= intervals[i][start]，所以必須用end來做遞增排序。==



### 計算重疊區間個數 method2

追蹤interval前後，統計目前overlap的個數。
這邊例子的定義是[start, end)。每加入一個新的interval，就重新計算在這個interval中經過的point都加1。


// 因為使用了prev，避免prev(m.begin())的情況，所以加入{-1 , 0}
map<int, int> m{{-1, 0}}; // value, count
void book(int start, int end) 
{
    // 找出新的interval起點和結束的插入點。count為前一個的值
    // 使用emplace可以少一次copy，必且回傳插入點的iterator
    auto s = m.emplace(start, prev(m.lower_bound(s))->second);
    auto e = m.emplace(end, prev(m.lower_bound(e))->second);
    // 走訪新interval中的所有值
    for(auto it = s.first; it != e.first; ++it) {
        it->second++;
    }
}

### 計算重疊區間個數 method3

上面的方法是不要斷更新，新增加interval中的所有點。另一種方法是只跟新新增加interval的前後點，開始點+1，結束點-1。但是這樣的缺點是必須從頭跑到結束點，才可以知道overlap的個數。


map<int, int> m; // value, count
int book(int start, int end)
{
    m[start]++;
    m[end--];
    int overlap{0}, maxans{0};
    for(auto ref : m) {
        overlap += ref.second;
        if(ref.first >= start) 
            maxans = max(maxans, overap);
        if(ref.first == end) break;
    }
    return maxans;
}

#### [452. Minimum Number of Arrows to Burst Balloons](https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/)
使用最少的arrows來刺破所有的氣球。
> 1. 先將氣球根據end做遞增排序。
> 2. 計算有overlap的氣球個數，就是最少的arrows數。

enum st{start, end};
int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(), points.end(), [&](vector<int>& a, vector<int>& b){
        return a[1] < b[1];
    });
    int ans = 1, cur = 0;
    for(int i = 1; i < points.size(); ++i) {
        if(points[cur][end] >= points[i][start] ) continue;
        else {
            ans++;
            cur = i;
        }
    }
    return ans;
}

2023/01/05
> 1. 因為忘了以前怎麼寫的，所以從頭思考。
> 2. 這種題目一定是先排序。
> 3. 直接判斷重複區域，如果沒重複區域就表示需要另一個arrow。
> 4. 下面是我第一個版本

int findMinArrowShots(vector<vector<int>>& points) {
    int sz = points.size();
    if(sz == 1) return 1;
    sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b){
        return a[1] < b[1];
    });
    int ans{0};
    vector<int> cur = points[0];
    for(int i = 1; i < sz; ++i) {
        cur[0] = max(cur[0], points[i][0]);
        cur[1] = min(cur[1], points[i][1]);
        if(cur[1] < cur[0]) { // 區域沒重疊
            ans++;
            cur = points[i];
        }
    }
    return ans + 1;
}

其中cur[1]和cur[0]可以帶入上面的運算

if(min(cur[1], points[i][1]) < max(cur[0], points[i][0])) {

因為是照end排序，所以後來的points[i][1]一定比cur[1]大，所以不需要min()操作。

if(cur[1] < max(cur[0], points[i][0])) {

如果我們在sort的時候也指定start的排法，讓比較後面出現的排在後面，我們就可以省掉max運算。

sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b){
    if(a[1] < b[1]) return true;
    else if(a[1] == b[1]) return a[0] < b[0];
    else return false;
});

所以會變成

if(points[cur][1] < points[i][0]) {

最後觀察一下，其實不需要儲存vector<int> cur，只需要index即可。所以變成以下的code。

int findMinArrowShots(vector<vector<int>>& points) {
    int sz = points.size();
    if(sz == 1) return 1;
    sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b){
        if(a[1] < b[1]) return true;
        else if(a[1] == b[1]) return a[0] < b[0];
        else return false;
    });
    int ans{0}, cur = 0;
    for(int i = 1; i < sz; ++i) {
        if(points[cur][1] < points[i][0]) {
            ans++;
            cur = i;
        }
    }
    return ans + 1;
}

上面的code的解釋就會變成，因為end排序過，所以重疊區域的end一定是第一個interval的end，只要比下一個interval的start還小表示沒交集，則需要一個arrow。

### Group Intervals，不重疊的interval組成一個group。
通常這類的題目會問最少的group，因為最多的group就是每個interval自己一組。這個問題是Greedy問題。因為每個不重疊的群組裡面越多interval越好，這樣group就會最少。

==Policy==
+ 怎樣才可以最少Group?
+ 一個group內塞入越多的interval越好。
+ 表示一個group內，空格越少越好。
+ 當一個interval結束後，馬上插入下一個start最近的interval。
+ 因為必須知道start的順序，所以對intervals根據start排序。
+ 因為必須知道最早結束的interval，所以使用min-heap。

從下圖可知，當[1, 4]被放進group之後，下一個會選[6, 9]，因為這樣空格只有2最少，如果選[7, 10]空格會變成3，不是local optimal不符合Greedy。當每個group的空格都最少，就會是最少的group(global optimal)。


#### [2406. Divide Intervals Into Minimum Number of Groups](https://leetcode.com/problems/divide-intervals-into-minimum-number-of-groups/)
把給定的vector<vector<int>> intervals分類成不重疊的群組，且群組的數量是最少的。

int minGroups(vector<vector<int>>& intervals) {
    sort(begin(intervals), end(intervals));  //O(NlogN)
    priority_queue<int, vector<int>, greater<int>> pq; //min-heap
    for(const auto& itv : intervals) { // O(NlogN)
        if(!pq.empty() && pq.top() < itv[0]) pq.pop();
        pq.push(itv[1]);
    }
    // time  : O(NlogN + NlogN) = O(NlogN)
    // space : O(N)
    return pq.size();
}

#### [253. Meeting Rooms II](https://leetcode.com/problems/meeting-rooms-ii/)
每個會議有開始和結束時間，給你一個會議列表vector<vector<int>> intervals，試問需要最少的會議室?

int minMeetingRooms(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end()); //O(NlogN)
    priority_queue<int, vector<int>, greater<int>> q; // min-heap
    for (const auto& interval : intervals) { // O(NlogN)
        if (!q.empty() && q.top() <= interval[0]) q.pop();
        q.push(interval[1]);
    }
    // time  : O(NlogN + NlogN) = O(NlogN)
    // space : O(N)
    return q.size();
}

### 最少intervals可以涵蓋所有的範圍。
常常會出現的題目，使用最少的intervals來涵蓋指定的範圍。
這是一種Greedy的題目。
1. 先對intervals根據start來排序。
2. 找出能涵蓋start的情況下

   intervals[i][0] <= start

最遠可以到達的interval。

   end = max(end, intervals[i][1]);

3. 把start改成最遠可以到達的end。

   start = end; 

#### [1326. Minimum Number of Taps to Open to Water a Garden](https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/description/)

class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        vector<vector<int>> intervals;
        for(int i = 0; i < ranges.size(); ++i)
            intervals.push_back({i - ranges[i], i + ranges[i]});
        sort(begin(intervals), end(intervals)); // sort by start point
        int count{}, start{}, end{}, i{};
        while(end < n) {
            // 從可以包含start的情況下，找出最遠的end
            for(; i < ranges.size() && intervals[i][0] <= start; ++i)
                end = max(end, intervals[i][1]);
            if(start == end) return -1; // 無法前進
            start = end;
            count++;
        }
        return count;
    }
};

### Problems
#### [2276. Count Integers in Intervals](https://leetcode.com/problems/count-integers-in-intervals/)

class CountIntervals {
    map<int, int> m; 
    int cnt = 0;
    bool isIntersect(const auto& it, int left, int right) {
        return max(it->first, left) <= min(it->second, right);
    }
public:
    CountIntervals() {
        
    }
    
    void add(int left, int right) {
        auto it = m.upper_bound(left);
        // 前一個和新增的有重疊，則把it移動到前一個
        if(it != m.begin() && isIntersect(prev(it), left, right))
            it = prev(it);
        // 目前區域和新增的有重疊，則合併
        while(it != m.end() && isIntersect(it, left, right)) {
                left = min(left, it->first);
                right = max(right, it->second);
                cnt -= it->second - it->first + 1;
                auto nxt = next(it);
                m.erase(it);
                it = nxt;
        }
        cnt += right - left + 1;
        m[left] = right;
    }
    
    int count() {
        return cnt;
    }
};

###### tags: `leetcode` `刷題`