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 <= 100001 <= N <= 100000
1 <= B <= 10000Input Format
First argument is an integer array A where A[i] is either 0 or 1.
Second argument is an integer B.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.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 = 3Input 1:
A = [ 0, 0, 1, 1, 1, 0, 0, 1].
B = 3
Input 2:
A = [ 0, 0, 0, 1, 0].
B = 3Example Output
Output 1:
2
Output 2:
-1Output 1:
2
Output 2:
-1Example 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.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
}
}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
}
}