[BOJ]白俊1931号会議室(Python)の手配

4838 ワード
白駿 boj python greedy algorithm Sort コーディングテスト テキストリンク

質問する


会議室があり、それを使用するN個の会議について、会議室使用表を作成します.各会議Iには、開始時間と終了時間があり、各会議が重複しないように、会議室の最大数を見つけます.しかし、会議が始まると、途中で中断することはできません.一つの会議が終わると同時に、次の会議が始まる可能性があります.会議の開始時間と終了時間は同じかもしれません.この場合、最初から終わっていると考えられます.

入力

  • 第1行は、会議数N(1≦N≦100000)を与える.
  • 行目からN+1行目にかけて、各会議の情報が与えられます.これは、会議の開始時間と終了時間を与えるスペースです.
  • 開始時間および終了時間(2^31)−1は、自然数または0以下である.

    • しゅつりょく

  • の最初の行の最大使用可能な会議数を出力します.

    • 例


    入力します。

    11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

    出力します。

    4

    に答える

    n = int(input())

meeting = [list(map(int, input().split())) for _ in range(n)]
meeting.sort(key=lambda x: (x[1], x[0]))	# 회의 정렬. 끝나는 시간 오름차순 기준.
availableMeeting = 0			# 가능한 회의 수
numOfMeeting = len(meeting)		# 총 회의 수
endTime = meeting[0][0]			# 현재 회의 끝나는 시간.

for i in range(numOfMeeting):		# 모든 회의 확인
    if endTime > meeting[i][0]:		# 현재 순서 회의가 현재 진행중인 회의와 시간이 겹치면 패스
        continue
        
    # 회의 시간이 겹치지 않은 경우
    endTime = meeting[i][1]		# 회의 끝나는 시간 업데이트		
    availableMeeting += 1		# 가능한 회의 수 1 증가

print(availableMeeting)
    会議の終わりの早い順に手配する.
    当初は会議の長さは短い順だったが、変数が出て失敗した.
    開始時間順にやったけど失敗した
    終了時間順にやってくれて良かったです.
    会議の終了時間順に並べて、会議時間が重複しない場合に会議を行います.
    効率を向上させるemacs構成×10
    Netty - Buffer 1