アルゴリズムの学習の為、LeetCodeを学習しています。
今回は貪欲アルゴリズムを用いて解いたものです。
解答（Go言語）
早速解答から
func findMinArrowShots(points [][]int) int {
if len(points) == 0 {
return 0
}
sort.Slice(points, func(i, j int) bool {
return points[i][1] < points[j][1]
})
arrows := 1
position := points[0][1]
for i := 1; i < len(points); i++ {
if points[i][0] <= position {
continue
}
arrows++
position = points[i][1]
}
return arrows
}解説
sort.Slice(points, func(i, j int) bool {
return points[i][1] < points[j][1]
})この部分で
与えられた風船の最大値が昇順になるように並び替えています。
並び変えることで、次に参照する風船の最小値(point[0])と今のポジションの最大値を比較する操作を繰り返すだけでよくなりました。
①次に参照するスライスの最小値<ポジションの最大値
この場合は今のポジションに矢を放てば参照する風船も割ることができます。
if points[i][0] <= position {
continue
}
②次に参照するスライスの最小値>ポジションの最大値
この場合は今のポジションに矢を放っても参照する風船を割ることができません。
矢の本数を増やしてポジションをこの参照している風船の最大値に合わせます。
風船の最大値を昇順に並び替えた後に参照しているので、「次に参照する風船の最小値と今のポジションの最大値を比較する」ことを繰り返せばよいです。
arrows++
position = points[i][1]考察
この問題で一番重要なのは「昇順に風船を並び替える」という発想だと思います。
自分が書いたコードはもともと以下のようなものでした。
風船を順番に参照していき、共通範囲を記録し、既存の共通範囲にかぶらないときに新しく共通範囲を増やす操作をしています。
このやり方だとできませんでした。次の操作が終わった後にすべての共通範囲をもう一度考え直す必要があるためです。
動的計画法みたいな考え方ですが、これが適用できるのは次の操作で前の操作を再度考察する必要がない時のみですね。
func findMinArrowShots(points [][]int) int {
var commonPoint [][]int
for _,point := range points {
min := point[0]
max := point[1]
isCommon := false
for _,cPoint := range commonPoint{
if max < cPoint[0] || cPoint[1]< min{
continue
}else if min < cPoint[0]{
cPoint[1] = max
isCommon = true
break
}else if cPoint[1] < max{
cPoint[0] = min
isCommon = true
break
}else if cPoint[0]<=min && max<=cPoint[1]{
cPoint[0] = min
cPoint[1] = max
isCommon = true
break
}
}
if isCommon == false{
commonPoint = append(commonPoint,point)
}
}
return len(commonPoint)
}
