[伯俊]会議室の手配(1931)-python

▼▼問題

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

🎈 入力

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

🎈 しゅつりょく

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

🎈 I/O例

<入力>
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
<出力>
4

👩‍💻 マイコード

この問題はグリディアルゴリズムで解いた.最初は複雑な問題だと思いましたが、ちょっと難しかったです.Pythonのソートをよく知っていれば、簡単に解決できます.この問題で発見されたルールは以下の通りである.
早く終わる会議ほど、後の会議が多くなります.

以降の会議開始時間は、前回の会議終了時間に最も近い時間でなければならない.

の開始時間が同じ場合、終了時間の早い会議を開くべきである.

from collections import deque
N = int(input()) # 회의 수
time_arr = [] # 시간 배열
result = 0 # 회의 최대 개수

for i in range(N):
    time_arr.append(tuple(map(int, input().split())))

time_arr = sorted(time_arr, key=lambda x: x[1])
tmp = 0

for i in time_arr:
    start_time = i[0]
    finish_time = i[1]

    if start_time >= tmp:
        result += 1
        tmp = finish_time

print(result)

最初は上のように編んだとき、結果はすべて正しいので、正しい答えだと思っていたが、結果は間違っていた.何が問題なのか確認したところ、開始時間が同じ場合は考えられませんでした.開始時間が同じである場合、lambda x:x[1]、x[0](x[1]は(x[1]の昇順で配列され、x[1]はx[0]の昇順で配列される).表示されるように、メモして並べ替えます.

from collections import deque
N = int(input()) # 회의 수
time_arr = [] # 시간 배열
result = 0 # 회의 최대 개수

for i in range(N):
    time_arr.append(tuple(map(int, input().split())))

time_arr = sorted(time_arr, key=lambda x: (x[1], x[0])) # 두 번째 원소로 정렬하고 두 번째 원소가 같은 경우 첫 번째 원소로 정렬
tmp = 0

for i in time_arr:
    start_time = i[0]
    finish_time = i[1]

    if start_time >= tmp:
        result += 1
        tmp = finish_time

print(result)