백준 17262 : 팬덤이 넘쳐흘러(그리디)***

 

www.acmicpc.net/problem/17262

17262번: 팬덤이 넘쳐흘러

 

Input : 만나야 하는 팬의 수 N

          [ s, e ] 팬이 머무는 시간의 수

 

Output: 머무르는 최소의 시간

      

풀이:

직관적으로 보면, start = 제일 일찍 집 가는 사람 ~~  end = 제일 늦게 오는 사람으로 하면 된다.

하지만, 위 문장을 그대로 코드화 하면 다음과 같은 경우에 문제가 생긴다.

(start = 보라색 포인트, end = 파란색 포인트) 가 되어야 하는데,

(start = 보라색 포인트, end = 노란색 포인트) 가 된다.

 

 

따라서 ,

que = 팬들( 집 가는 시간 기준으로 sort)

start_time = 제일 일찍 집 가는 사람

start 시간에 만날 수 있는 팬들을 que에서 제거

end_time = 남은 팬들 중 제일 늦게 오는 사람으로 하면 된다.

 

 

def solve(Fans):
    que = sorted(Fans,key = lambda x:x[1])
    if que == []:return 0
    start = que[0][1]
    now = que[0][1]
    while que:
        s,e = que[0]
        if s<=now and e>=now : que.pop(0)
        else: 
            que = sorted(que,key = lambda x:x[0])
            now = que[-1][0]
            break
    return now-start

if __name__=='__main__':
    N = int(input())
    Fans = []
    for i in range(N):
        s,e = map(int,input().split())
        Fans.append([s,e])
    print(solve(Fans))