Skip to main content

assign_to_columns

Function assign_to_columns 

Source
pub fn assign_to_columns(heights: &[i32], n_cols: usize) -> Vec<Placement>
Expand description

子の高さ列を受け取り、各子をどの列のどの高さへ置くかを決める(純粋関数)。

不変条件 M-6 のとおり「その時点で高さが最小の列」へ順に入れる貪欲法。 同じ高さの列が複数あるときは左の列を優先する(見た目の安定のため。 右から埋まると 1 件だけのときに不自然に右へ寄る)。

返り値の長さは heights と同じ。列数が 0 のときは全て 0 列目へ倒す。

計算量: O(子数 × 列数)。列数は高々数十なので実用上問題ない。