# P6-16
## Sol1.使用邊界條件二分搜
題目link: https://judge.tcirc.tw/ShowProblem?problemid=d118
AC (38ms, 1.9MB)

#include<bits/stdc++.h>
using namespace std;
const int N = int(1e5+5);
int n, dp[N] = {0};
typedef struct{
    int s, t, e;
}seg;
seg s[N];
bool cmp(seg s1, seg s2){
    return s1.t < s2.t;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> s[i].s >> s[i].t >> s[i].e;
    }
    dp[0] = 0;
    s[0].e = 0;
    s[0].t = -1;
    sort(s+1, s+n+1, cmp);
    for(int i = 1;i <= n;i ++){
        int l = 1;
        int r = n;
        while(l < r){
            int mid = (l + r) / 2;
            if (s[mid].t < s[i].s)
                l = mid+1;
            else
                r = mid;
        }
        dp[i] = dp[l-1] + s[i].e;
        if (dp[i] < dp[i-1]) dp[i] = dp[i-1];
    }
    cout << dp[n];
}

## Sol2.使用lower_bound()
AC (34ms, 1.1MB)

#include<bits/stdc++.h>
using namespace std;
const int N = int(1e5+5);
int n, dp[N] = {0};
typedef struct{
    int s, t, e;
}seg;
seg s[N];
bool cmp(seg s1, seg s2){
    return s1.t < s2.t;
}
bool cmp2(seg p, int x){
    return p.t < x;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> s[i].s >> s[i].t >> s[i].e;
    }
    dp[0] = 0;
    s[0].e = 0;
    s[0].t = -1;
    sort(s+1, s+n+1, cmp);
    for(int i = 1;i <= n;i ++){
        int l = lower_bound(s, s + i, s[i].s, cmp2) - s;
        dp[i] = dp[l-1] + s[i].e; 
        if (dp[i] < dp[i-1]) dp[i] = dp[i-1];
    }
    cout << dp[n];
}

## Sol3.使用跳躍二分搜
AC (39ms, 1.8MB)

#include<bits/stdc++.h>
using namespace std;
const int N = int(1e5+5);
int n, dp[N] = {0};
typedef struct
{
    int s, t, e;
} seg;
seg s[N];
bool cmp(seg s1, seg s2)
{
    return s1.t < s2.t;
}
bool cmp2(seg p, int x)
{
    return p.t < x;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> s[i].s >> s[i].t >> s[i].e;
    }
    dp[0] = 0;
    s[0].e = 0;
    s[0].t = -1;
    sort(s+1, s+n+1, cmp);
    for(int i = 1; i <= n; i ++)
    {
        int l = 0;
        for (int jump=i/2; jump>0; jump>>=1)
        {
            while (l+jump<i && s[l+jump].t<s[i].s)
                l += jump;
        }
        dp[i] = dp[l] + s[i].e;
        if (dp[i] < dp[i-1]) dp[i] = dp[i-1];
    }
    cout << dp[n];
}