Minimum Light Bulbs Needed To Light The Whole Corridor


Given :

  • An array of N cell(s) in a jail.
  • Each cell has a working bulb denoted by 1 and a faulty bulb denoted by 0.
  • Power of each bulb is P.
    A bulb with power P at position X can light cells in range [ X - P + 1, …, X + P - 1 ]
  • Initially all bulbs are switched OFF.

Objective : Return the minimum number of lights that should be switched ON to light the whole corridor. Return -1 if the whole corridor cannot be lighted.


Consider the below example:
Power of each bulb is 3.
Bulbs in cells [ 2, 3, 4 ] are in working condition.

Light_Bulbs

#include<iostream>
#include<vector>

using namespace std;

int solve (vector<int> &jail, int power) {

    int cells = jail.size();
    int count = 0;
    int pos = 0;
    bool lit = false;

    while (pos < cells) {

        lit = false;
        int from_right = min (cells-1, pos + power - 1);
        int from_left =  max (0, pos - power + 1);

        // Check from right
        for (int cell_no = from_right; cell_no >= pos; cell_no--) {
            if (A[cell_no] == 1) {
                count++;
                pos = cell_no + power; // new pos of the next cell to be lit.
                lit = true;
                break;
            }
        }

        if (!lit) {
            // Check from left;
            for (int cell_no = pos-1; cell_no >= from_left; cell_no--) {
                if (A[cell_no] == 1) {
                    count++;
                    pos = cell_no + power; // new pos of the next cell to be lit.
                    lit = true;
                    break;
                }
            }
        }

        if (!lit)
            return -1;
    }
    return count;
}

int main() {

    vector<int> jail1 = {0, 0, 1, 1, 1, 0, 0};
    cout << "Bulbs switched on : " << solve(jail1, 3) << endl;

    vector<int> jail2 = {1, 1, 1};
    cout << "Bulbs switched on : " << solve(jail2, 3) << endl;
  
    vector<int> jail3 = {0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0};
    cout << "Bulbs switched on : " << solve(jail3, 12) << endl;

    vector<int> jail4 = {0, 1, 0};
    cout << "Bulbs switched on : " << solve(jail4, 1) << endl;

    return 0;
}

Output

Bulbs switched on : 2
Bulbs switched on : 1
Bulbs switched on : 2
Bulbs switched on : -1


Copyright (c) 2019-2022, Algotree.org.
All rights reserved.