Skip to content

[Algorithm] MaxNonoverlappingSegmentsย #150

@hwangJi-dev

Description

@hwangJi-dev

๐Ÿ’ฌย ๋ฌธ์ œ

https://app.codility.com/programmers/lessons/16-greedy_algorithms/max_nonoverlapping_segments/


๐Ÿ’ฌย Idea

  • ์„ ๋ถ„์˜ ์ค‘์ฒฉ๋˜์ง€ ์•Š์€ ์ตœ๋Œ€๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ. ๋ฐฐ์—ด์˜ ์ฒซ end์™€ ๋‹ค์Œ ์ธ๋ฑ์Šค์˜ start๋ฅผ ๋น„๊ตํ•ด ์ตœ๋Œ€ ๊ฐœ์ˆ˜๋ฅผ ์ฐพ์•„์ฃผ๋ฉด ๋œ๋‹ค.

๐Ÿ’ฌย ํ’€์ด

public func solution(_ A : inout [Int], _ B : inout [Int]) -> Int {
    if A.isEmpty { return 0 }
    
    var end = B[0]
    var cnt = 1
    
    for i in 1..<A.count {
        if A[i] > end {
            cnt += 1
            end = B[i]
        }
    }
    
    return cnt
}

์‹œ๊ฐ„ ๋ณต์žก๋„ : O(N)

ํ‰๊ฐ€ํ‘œ : https://app.codility.com/demo/results/trainingR64NKR-G29/

Metadata

Metadata

Assignees

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions