<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
::-webkit-scrollbar {
width: 10px;
}
::-webkit-scrollbar-track {
background: transparent;
}
::-webkit-scrollbar-thumb {
background: linear-gradient(180deg, #2BE8CF60 0%, #2B83E860 100%);
border-radius: 3px;
}
::-webkit-scrollbar-thumb:hover {
background: linear-gradient(180deg, #2BE8CF95 0%, #2B83E895 100%);
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000036;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}

</style>
###### tags: `Algorithm_Lab`

# Interval and Interval Graph 結報
## OJ AC截圖

## Code

// UVA 12694
#include <bits/stdc++.h>
using namespace std;

bool compare(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}
int schedule(vector<pair<int, int>> interval) {
    sort(interval.begin(), interval.end(), compare);
    int f = interval[0].second, ans = 1;
    for (int i = 1; i < interval.size(); ++i)
        if (interval[i].first >= f)
            ++ans, f = interval[i].second;
    return ans;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        vector<pair<int, int>> interval;
        int s, f;
        cin >> s >> f;
        while (s || f) {
            interval.push_back({s, f});
            cin >> s >> f;
        }
        cout << schedule(interval) << endl;
    }
}

### $n$ is input's size
## 空間複雜度分析
* f, ans, i
* $O(1)$

## 時間複雜度分析
### Best Case && Worst Case
* sort($O(n\log n)$)
* 走訪一遍(n)
* $O(n\log n)$

## DATE
2023/06/02