Skip to content

11360: 【原1360】偶像丁姐的烦恼

题目

题目描述

author: SSY 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1360

Description

成为LL冠军的人气偶像丁姐最近比较烦，许多商业活动找上门来。因为每次商业活动给的毛爷爷都一样，所以丁姐希望能够尽可能多的参加这些活动。然而，商业活动的起止时间并不由丁姐说了算，因此丁姐想写一个程序，求出他最多能够参加的商业活动的数量。

Input Format

第一行一个数n，表示可选活动的数量。

接下n行每行两个数，表示每个活动开始时间t1_i和结束的时间t2_i。

Output Format

一个数字，表示丁姐最多能够参加的活动的数量。

Sample Input

10
0 3
0 5
10 13
12 15
2 6
4 8
9 11
13 18
14 16
15 20

Sample Output

5

Hint

样例选取的活动时间为：(0, 3), (4, 8), (9, 11), (12, 15), (15, 20)

n≤100000

0≤t1_i＜t2_i≤1000000

BugenZhao's solution 

//
// Created by BugenZhao on 2019/3/17.
//
// 线段覆盖 右端点贪心

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

static const auto _____ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

class Period {
public:
    int a;
    int b;

    bool operator<(const Period &rhs) const {
        if (b < rhs.b)
            return true;
        if (rhs.b < b)
            return false;
        return a < rhs.a;
    }
};

int main() {
    int n;
    cin >> n;
    auto periods = new Period[n];
    for (int i = 0; i < n; ++i) {
        cin >> periods[i].a;
        cin >> periods[i].b;
    }
    sort(periods, periods + n);

    int current = periods[0].b;
    int count = 1;
    for (int j = 1; j < n; ++j) {
        if (periods[j].a >= current) {
            ++count;
            current = periods[j].b;
        }
    }
    cout << count << endl;
    delete[] periods;
    return 0;
}

ligongzzz's solution 

#include "iostream"
#include "cmath"
#include "cstdio"
using namespace std;

int times[100009][2] = { 0 };

template <class T>
void quick_sort(T start, T end) {
    if (start == end)
        return;
    auto i = start, j = end;
    --j;
    if (i == j)
        return;
    //交换
    auto key = (*start)[1];
    auto tmp = (*start)[0];
    for (bool status = true; i != j;) {
        if (status) {
            if ((*j)[1] < key) {
                (*i)[0] = (*j)[0];
                (*i)[1] = (*j)[1];
                ++i;
                status = false;
            }
            else
                --j;
        }
        else {
            if ((*i)[1] > key) {
                (*j)[0] = (*i)[0];
                (*j)[1] = (*i)[1];
                --j;
                status = true;
            }
            else
                ++i;
        }
    }
    (*i)[0] = tmp;
    (*i)[1] = key;
    //递归
    quick_sort(start, i + 1);
    quick_sort(i + 1, end);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &times[i][0], &times[i][1]);
    }
    //排序
    quick_sort(times, times + n);
    int ans = 0;
    for (int i = 0, cur_time = 0; i < n; ++i) {
        if (times[i][0] >= cur_time) {
            ++ans;
            cur_time = times[i][1];
        }
    }

    cout << ans;

    return 0;
}

q4x3's solution 

/**
 * 模拟
 * 根据活动结束时间排序
 * 结束最早的先安排上
 * 再看第二早的能不能安排
 * 不能就下一个
 * 为了方便用排序模板封装了一下
 **/
#include <iostream>

using namespace std;

template <typename T>
void merge(int lo, int mi, int hi, T* a)
{
    T* A = a + lo;
    int lb = mi - lo;
    T* B = new T[lb];
    T* BB = B;
    for(int i = 0;i < lb;++ i)
        B[i] = A[i];
    int lc = hi - mi;
    T* C = a + mi;
    int cnt = 0;
    while(1) {
        if ((lb == 0) && (lc == 0)) break;
        if (lb == 0) {
            A[cnt] = C[0];
            ++ cnt; ++ C; -- lc;
        }
        else if (lc == 0) {
            A[cnt] = B[0];
            ++ cnt; ++ B; --lb;
        }
        else {
            if(B[0] < C[0]) {
                A[cnt] = B[0];
                ++ cnt; ++ B; -- lb;
            }
            else {
                A[cnt] = C[0];
                ++ cnt; ++ C; -- lc;
            }
        }
    }
    delete []BB;
}

template <typename T>
void mergeSort(int lo, int hi, T* A)
{
    if(hi - lo < 2) return;
    int mi = (lo + hi) / 2;
    mergeSort(lo, mi, A); mergeSort(mi, hi, A);
    merge(lo, mi, hi, A);
}

class node {
    public:
    int t1, t2;
    node():t1(0), t2(0) {}
    node(const node &obj):t1(obj.t1), t2(obj.t2) {}
    bool operator<(const node &obj) {
        return t2 < obj.t2;
    }
    bool operator>(const node &obj) {
        return t2 > obj.t2;
    }
    bool operator==(const node &obj) {
        return t2 == obj.t2;
    }
    friend istream& operator>>(istream &in, node &obj);
};

istream& operator>>(istream &in, node &obj) {
    in >> obj.t1 >> obj.t2;
    return in;
}

int n, ans = 1;
node a[100233];

int main() {
    cin >> n;
    for(int i = 0;i < n;++ i)
        cin >> a[i];
    mergeSort(0, n, a);
    int curt2 = a[0].t2;
    for(int i = 0;i < n - 1;++ i) {
        if(a[i + 1].t1 >= curt2) {
            ++ ans;
            curt2 = a[i + 1].t2;
        }
    }
    cout << ans << endl;
    return 0;
}

skyzh's solution

#include <iostream>
#include <algorithm>
using namespace std;

struct Period {
    int start, end;
};

Period D[100000];

bool cmp(const Period& a, const Period& b) {
    if (a.end == b.end) return a.start > b.start;
    return a.end < b.end;
}

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> D[i].start >> D[i].end;
    }
    int idle = -1;
    int p = 0;
    sort(D, D + N, cmp);
    for (int i = 0; i < N; i++) {
        if (idle <= D[i].start) {
            ++p;
            idle = D[i].end;
        }
    }
    cout << p << endl;
    return 0;
}

victrid's solution 

#include <iostream>
using namespace std;
struct t {
    int t1;
    int t2;
};
t* MergeSort(t* list, int listSize) {
    if (listSize == 1)
        return list;
    if (listSize == 2) {
        if (list[0].t2 > list[1].t2) {
            t temp  = list[0];
            list[0] = list[1];
            list[1] = temp;
            return list;
        }
        return list;
    }
    t* tmplist = new t[listSize];
    t* llst    = MergeSort(list, listSize / 2);
    t* rlst    = MergeSort(list + listSize / 2, listSize - listSize / 2);
    int lct = 0, rct = 0;
    while (lct + rct != listSize) {
        if ((llst[lct].t2 <= rlst[rct].t2 && lct < listSize / 2) || rct >= listSize - listSize / 2) {
            tmplist[lct + rct] = llst[lct];
            lct++;
        } else {
            tmplist[lct + rct] = rlst[rct];
            rct++;
        }
    }
    for (int i = 0; i < listSize; i++) {
        list[i] = tmplist[i];
    }
    return list;
}
inline int maxi(int i1, int i2) {
    return i1 > i2 ? i1 : i2;
}
int main() {
    int n;
    cin >> n;
    t *timeset = new t[n], *moveptr = timeset;
    for (int i = 0; i < n; i++) {
        cin >> timeset[i].t1;
        cin >> timeset[i].t2;
    }
    MergeSort(timeset, n);
    int* totalis = new int[timeset[n - 1].t2 + 1];
    totalis[0]   = 0;
    for (int i = 1; i < timeset[n - 1].t2 + 1; i++) {
        while (moveptr->t2 < i) {
            moveptr++;
        }
        totalis[i] = totalis[i - 1];
        while (moveptr->t2 == i) {
            totalis[i] = maxi(totalis[i], totalis[moveptr->t1] + 1);
            moveptr++;
        }
    }
    cout << totalis[timeset[n - 1].t2];
    return 0;
}

yyong119's solution 

#include <cstdio>
#include <algorithm>
#define MAX_N 100010
using namespace std;
struct Node {
    int x, y;
    bool operator<(const Node &p) const { return y < p.y; }
} a[MAX_N];
int n, cnt, cur_r;
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    // return res * flag;
    return res;
}
int main() {
    n = read();
    for (register int i = 0; i < n; ++i) a[i].x = read(), a[i].y = read();
    sort(a, a + n);
    cur_r = a[0].y; cnt = 1;
    for (register int i = 1; i < n; ++i)
        if (a[i].x >= cur_r) {
            ++cnt;
            cur_r = a[i].y;
        }
    printf("%d", cnt);
    return 0;
}