출처: https://cses.fi/problemset/task/1629

문제 설명

In a movie festival n movies will be shown. You know the starting and ending time of each movie. What is the maximum number of movies you can watch entirely?

입력  

The first input line has an integer n: the number of movies.

After this, there are n lines that describe the movies. Each line has two integers aa and bb: the starting and ending times of a movie.

출력

Print one integer: the maximum number of movies.

입력 예

3
3 5
4 9
5 8

출력 예

2

제약조건

  • 1 <= n <= 2x10^5
  • 1 <= a < b <= 10^9

문제 풀이 내용

영화가 끝나는 시간을 기준으로 정렬한다.

영화 끝나는 시간이 다음 영화 시작 시간 전에 끝나면, 볼 수 있는 영화편수를 증가시키고, 영화 끝나는 시간을 다음 영화 시간으로 갱신한다.  

프로그램 내용

더보기 
...
    vector <pair<int, int>> m_time;

    for(int idx=0; idx < n_movie; ++idx)
        int start_time, end_time; 
        m_time.push_back({end_time, start_time});

    sort(m_time.begin(), m_time.end()); /// sort by end_time 

    int c_movie=0;
    int time_now=0;
    for (int i = 0; i< n_movie; ++i)
        /// start_time > time_now 
        /// time_now = end_time, increase counter
        if (m_time[i].second >= time_now)
            time_now = m_time[i].first;
            c_movie++;
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Maximum Subarray Sum (1643)  (0) 2019.09.26
CSES 2. Sum of Two Values (1640)  (0) 2019.09.26
CSES 2. Restaurant Customers (1619)  (0) 2019.09.25
CSES 2. Concert Tickets (1091)  (0) 2019.09.25
CSES 2. Ferris Wheel (1090)  (0) 2019.09.25

출처: https://cses.fi/problemset/task/1619

문제 설명

You are given the arrival and leaving times of n customers in a restaurant.

What was the maximum number of customers?

입력 

The first input line has an integer n: the number of customers.

After this, there are n lines that describe the customers. Each line has two integers a and b: the arrival and leaving times of a customer.

You may assume that all arrival and leaving times are distinct.

출력

Print one integer: the maximum number of customers.

입력 예

3
5 8
2 4
3 9

출력 예

2

제약조건

  • 1 <= n <= 2x10^5
  • 1 <= a < b <= 10^9

문제 풀이 

입력받은 시간들을 priority queue 에 저장한다.

단, 먼저 도착한 사람이 앞쪽에 나오도록 모두 음수로 만든다.

저장된 queue 의 제일 위쪽에 있는 자료를 확인해서, 도착 시간이면 +1, 떠난 시간이면 -1을 누적한다.

 

이렇게 누적한 손님 수중에서 가장 큰 값을 출력한다.

프로그램 내용

더보기 
...
    priority_queue<tuple<int, bool>> c_time;

    for(int idx=0; idx < n_Customer; ++idx)
        cin >> start_time >> end_time ;
        c_time.push({-start_time, true});
        c_time.push({-end_time, false});

    int ct_now=0;
    int ct_count=0;

    while (!c_time.empty())
        ct_now += get<1>(c_time.top()) ? 1 : -1; /// start__time +1, end_time -1
        c_time.pop();
        ct_count = max(ct_count, ct_now);

	cout << ct_count << endl;

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Sum of Two Values (1640)  (0) 2019.09.26
CSES 2. Movie Festival (1629)  (0) 2019.09.26
CSES 2. Concert Tickets (1091)  (0) 2019.09.25
CSES 2. Ferris Wheel (1090)  (0) 2019.09.25
CSES 2. Apartments (1084)  (0) 2019.09.24

출처: https://cses.fi/problemset/task/1091

문제 설명

There are n concert tickets available, each with a certain price. Then, m customers arrive, one after another.

Each customer announces the maximum price he or she is willing to pay for a ticket, and after this, they will get a ticket with the nearest possible price such that it does not exceed the maximum price.

입력

The first input line contains integers n and m: the number of tickets and the number of customers.

The next line contains n integers h_1,h_2,…,h_n: the price of each ticket.

The last line contains mm integers t_1,t_2,…,t_m: the maximum price for each customer.

출력

Print, for each customer, the price that they will pay for their ticket. After this, the ticket cannot be purchased again.

입력 예

5 3
5 3 7 8 5
4 8 3

If a customer cannot get any ticket, print −1.

출력 예

3
8
-1

제약조건

  • 1 <= n,m <= 2x10^5
  • 1 <= h_i, t_i <= 10^9

문제 풀이 

티켓 가격을 multiset에 저장하고, 희망 가격으로 lower_bound를 찾는다.

그 가격보다 낮은 가격이 있으면 출력하고, 없으면 -1을 출력한다.

프로그램 내용

더보기 
...
    multiset <long, greater<long>> tPrice;

    for (int in=0; in < nTicket; ++in)
        cin >> temp;
        tPrice.insert(temp);

    for (int id = 0; id < nCustomer; ++id)
        cin >> temp;
        auto low = tPrice.lower_bound(temp);
        if ( low == tPrice.end())
            cout << -1 << endl;
        else
            cout << *low << endl;
            tPrice.erase(low);
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Movie Festival (1629)  (0) 2019.09.26
CSES 2. Restaurant Customers (1619)  (0) 2019.09.25
CSES 2. Ferris Wheel (1090)  (0) 2019.09.25
CSES 2. Apartments (1084)  (0) 2019.09.24
CSES 2. Distinct Numbers (1621)  (0) 2019.09.24

+ Recent posts

티스토리툴바