---
# System prepended metadata

title: Interval and Interval Graph 結報
tags: [Algorithm_Lab]

---

<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截圖
![](https://hackmd.io/_uploads/SkKoXGvU3.png)

## Code
```cpp=
// 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