Algotree > Algorithms > Greedy > Minimum Light Bulbs Needed To Light The Whole Corridor

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