fork download
copy 
  1. def weighted_interval_scheduling_with_solution():
  2.     # 入力の読み込み
  3.     n = int(input())
  4.     jobs = []
  5.     for i in range(n):
  6.         s, f, v = map(int, input().split())
  7.         jobs.append((s, f, v, i + 1))  # 元の番号を保持
  8.  
  9.     # 終了時刻でソート
  10.     jobs.sort(key=lambda x: x[1])
  11.  
  12.     # p[i]: ジョブiと重ならない最大のインデックス
  13.     p = [-1] * n
  14.     for i in range(n):
  15.         for j in range(i - 1, -1, -1):
  16.             if jobs[j][1] <= jobs[i][0]:
  17.                 p[i] = j
  18.                 break
  19.  
  20.     # 動的計画法
  21.     opt = [0] * (n + 1)
  22.     for i in range(1, n + 1):
  23.         # ジョブi-1を選ぶ場合
  24.         include = jobs[i-1][2]
  25.         if p[i-1] != -1:
  26.             include += opt[p[i-1] + 1]
  27.         else:
  28.             include += opt[0]
  29.  
  30.         # ジョブi-1を選ぶ場合と選ばない場合の最大値
  31.         opt[i] = max(opt[i-1], include)
  32.  
  33.     # 最適解の復元
  34.     def find_solution(i):
  35.         if i == 0:
  36.             return []
  37.  
  38.         # ジョブi-1を選ぶ場合の価値
  39.         include = jobs[i-1][2]
  40.         if p[i-1] != -1:
  41.             include += opt[p[i-1] + 1]
  42.         else:
  43.             include += opt[0]
  44.  
  45.         # ジョブi-1を選ぶ場合
  46.         if include >= opt[i-1]:
  47.             if p[i-1] != -1:
  48.                 return find_solution(p[i-1] + 1) + [jobs[i-1][3]]
  49.             else:
  50.                 return [jobs[i-1][3]]
  51.         # ジョブi-1を選ばない場合
  52.         else:
  53.             return find_solution(i-1)
  54.  
  55.     solution = find_solution(n)
  56.  
  57.     # 出力
  58.     print(solution)
  59.  
  60. # プログラムの実行
  61. weighted_interval_scheduling_with_solution()
Success #stdin #stdout 0.07s 14004KB
comments (?)
stdin
copy 
10
3 9 2
5 6 3
1 10 4
4 5 3
6 13 5
4 8 5
3 19 8
6 16 6
9 11 4
3 8 6
stdout
copy 
[4, 2, 8]
https://ideone.com/YtbEvE
language:
Python 3 (python  3.12)
created:
15 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!