SeaCode

Appearance

Minimum Lights to Activate ​

Problem Description ​

There is a corridor in a Jail which is N units long. Given an array A of size N.

The ith index of this array is 0 if the light at ith position is faulty otherwise it is 1.

All the lights are of specific power B which if is placed at position X, it can light the corridor from [X-B+1, X+B-1].

Initially all lights are off.

Return the minimum number of lights to be turned ON to light the whole corridor or -1 if the whole corridor cannot be lighted.

Problem Constraints

1 <= N <= 100000
1 <= B <= 10000

Input Format

First argument is an integer array A where A[i] is either 0 or 1.
Second argument is an integer B.

Output Format

Return the minimum number of lights to be turned ON to light the whole corridor or -1 if the whole corridor cannot be lighted.

Example Input

Input 1:
A = [ 0, 0, 1, 1, 1, 0, 0, 1].
B = 3

Input 2:
A = [ 0, 0, 0, 1, 0].
B = 3

Example Output

Output 1:
2

Output 2:
-1

Example Explanation

Explanation 1:
In the first configuration, Turn on the lights at 2nd and 7th index. 
Light at 2nd index covers from [ 1, 5] and light at 7th index covers [6, 8].

Explanation 2:
In the second configuration, there is no light which can light the first corridor.

Solution ​

swift
import Foundation

class Solution {
	func solve(_ A: inout [Int], _ B: inout Int) -> Int {
        let len = A.count
        // var light = [Int:Int]
        var ret = 0
        
        var i = 0
        while i < len {
            var found = false
            
            //右边找
            for j in (0..<B).reversed() {
                var index = i + j 
                if index >= len {
                    continue
                }
                if A[index] > 0 {
                    ret += 1
                    i = index + B
                    found = true
                    break
                }
            }
            if found == true {
                continue
            }
            //右边没找到，左边找
            for j in (1..<B) {
                var index = i - j 
                if index < 0 {
                    break
                }
                if A[index] > 0 {
                    ret += 1
                    i = index + B
                    found = true
                    break
                }
            }
            if found == false { //左边也找不到
                return -1
            }
        }
        
        // var wait = 0
        // while wait < len {
        //     var found = false
        //     for j in (0..<B).reversed() {
        //         var index = wait + j 
        //         if index >= len {
        //             continue
        //         }
        //         if A[index] > 0 {
        //             ret += 1
        //             wait = index + B
        //             found = true
        //             break
        //         }
        //     }
        //     if found == false {
        //         return -1
        //     }
        // }
        // return ret
        
        
        // for i in 0..<len{
        //     if A[i] > 0 {
        //         ret += 1
        //         var left = max((i - B + 1),0)
        //         var right = min((i + B - 1),len - 1)          
        //         for j in left...right{
        //             light[j] += 1
        //         }
        //     }
        // }
        
        // for i in light {
        //     if i == 0 {
        //         return -1
        //     }
        // }
        
        // for (i,v) in A.enumerated() {
        //     if v > 0 {
        //         var left = max((i - B + 1),0)
        //         var right = min((i + B - 1),len - 1) 
        //         var down = true
        //         for j in left...right{
        //             if light[j] <= 1 {
        //                 down = false
        //                 break
        //             }
        //         }
                
        //         if down == true {
        //             ret -= 1
        //             for j in left...right {
        //                 light[j] -= 1
        //             }
        //         }
        //     }
        // }
        return ret
	}
}

References ​