[백준 20126] 교수님의 기말고사 C++

20126번 - 교수님의 기말고사

문제 이해

0 ~ S 안에 이미 존재하는 N개의 구간과 잡아야하는 구간의 길이 M이 주어진다.
다른 구간들과 겹치지 않는 가장 앞선 길이 M의 구간의 시작을 출력하면 된다.
(구간을 잡지 못하는 경우 -1)

접근

주어지는 구간을 시작 시간을 기준으로 정렬하고, 순회하며 찾아내자.

문제를 풀다 보니, while로 짜면서 priority_queue를 사용한 구현이 쉽게 떠올라 해당 방법을 사용했다.

정답 코드

#include <bits/stdc++.h>
#define fastio             \
  ios::sync_with_stdio(0); \
  cin.tie(0);              \
  cout.tie(0)
#define REP(i, x, y) for (int i = x; i < y; i++)
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define INF (~0U >> 2)
#define MAX 10000

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N, M, S;
// cpp에서 pair정렬은 앞부분 기준. pq는 큰 값이 위가 기본
// 작은 값을 위로 하기 위해 greater<int> 사용
priority_queue<pii, vector<pii>, greater<pii>> timeline;

void init() {
  cin >> N >> M >> S;
  while (N--) {
    int x, y;
    cin >> x >> y;
    timeline.push({x, x + y});
  }
}

void solve() {
  int start = 0;
  while (!timeline.empty()) {
    int end = start + M;
    pii next = timeline.top();
    timeline.pop();
    if (end > S) {
      start = -1;
      break;
    }
    if (end <= next.X)
      break;
    start = next.Y;
  }
  cout << (start + M <= S ? start : -1);
}

int main() {
  fastio;
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif

  init();
  solve();

  return 0;
}