seungriyou / algorithm-study

알고리즘 & SQL 문제 풀이 기록
https://leetcode.com/u/summer_y
0 stars 0 forks source link

[LC] 1353. Maximum Number of Events That Can Be Attended #81

Open seungriyou opened 5 months ago

seungriyou commented 5 months ago

https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/ similar to #70

[!tip] [프로그래머스] 디스크 컨트롤러 문제와 비슷한 것 같다.

Approach

greedy 문제이며, sorting 및 priority queue를 활용해야 한다.

현재 날짜에서 attend 가능한 event 중, 가장 먼저 종료될 event에 attend 한다!

  1. events를 시작 날짜 기준으로 오름차순 정렬reverse한다.

  2. event의 종료 날짜를 담을 min heap pq을 선언하고, pqevents가 모두 empty가 될 때까지 다음을 반복한다.

    1. pq가 비었다면, 현재 dayevents[-1][0]으로 설정한다.
    2. 현재 day와 같은 날짜에 시작하는 event의 종료 날짜를 pq에 담는다.
    3. pq(무조건 empty가 아님)에서 pop한다. 즉, 현재 날짜에서 attend 가능한 event 중 가장 먼저 종료될 event에 attend 한다.
    4. daycnt를 모두 증가시킨다.
    5. pq에서 종료 날짜가 현재 day 보다 이른 event는 삭제한다.
  3. cnt 값을 반환한다.


Complexity