211123-会議室の手配

2975 ワード
python アルゴリズム#アルゴリズム# テキストリンク

会議室の手配


質問する


会社に急用があって、多くのチームが会議をしました.しかし、会議室が1つしかないため、管理チームはできるだけ多くのチームが会議を開くことができる場合を選んで、会議室をこれらのチームに借りることにした.各チームは、会議の開始時間と終了時間を記入し、便利なチームが会議を終了すると仮定し、次のチームが会議を準備する時間は0です.また、会議の開始時間と終了時間は同じである可能性があります.
各チームがコミットした会議の開始時間と終了時間がarr(アレイ)の場合、ソリューション関数を完了し、会議を行うことができる最大チーム数を返します.

入力

  • 会議日程リスト個数:100000以下自然数
  • 会議開始時間(S)、終了時間(E)範囲:0<=S<=20000

    • しゅつりょく

  • 会議ができる最大チーム数

    • I/O例


    arrresult[[1, 2], [2, 4], [2, 2]]3[[1, 4], [2, 6], [4, 72

    のり付け


    1.解説

  • 会議終了時刻を基準として、昇順に並べ替え、可能な会議数を決定する.
  • 可能な会議の開始時間が前回の会議の終了時間以上であれば、会議を開くことができる.
  • 会議:[1,2],[2,2],[2,4]
  • 最終終了時間:0=>[1,2]:可能
  • 最終終了時間:2=>[2,2]:可能
  • 最終終了時間:2=>[2,4]:可能
  • 3会議開催可能

    • 2.プログラム

  • arr終了時刻、開始時刻順
  • 会議ごとに会議を開催できるかどうかを調べる
  • start>=last
  • 可能な会議であればlast変更
    • # 코드
def solution(arr):
    answer = 0
    # 종료 시각을 기준으로 각 원소 정렬
    arr.sort(key = lambda x : (x[1], x[0]))
    last = 0    # 마지막 종료 시간

    # 각 회의에 따라 가능한지 조사
    for start, end in arr:
        # 시작 시간이 마지막 종료 시간 이상이라면 가능한 회의
        if start >= last:
            last = end  # 마지막 종료 시간 변경
            answer += 1 # 가능한 회의 개수 추가

    return answer

    アプリケーションサービスからの資格情報の抽出
    完全性を実現するためにコードを最適化