Given an input array A, your goal is to decide which stores to open, choosing among the values of i for which A[i] = 1. The only condition you must meet is that each pair of stores must be separated by at least three blocks. In other words, if you open stores on blocks x and y, then y − x ≥ 3. Your goal is to open as many stores as possible. For example, if n = 16 and A = [0,1,0,1,0,1,0,1,0,1,0,1,1,0,0,0], then the optimal solution is to open stores on blocks i = 2, 6, 10, 13, as illustrated in bold: A = [0,1,0,1,0,1,0,1,0,1,0,1,1,0,0,0]. Provide a greedy algorithm to solve this problem. Clearly explain how your algorithm works, why the running time of your algorithm is O(n), and show that the output is guaranteed to maximize the number of opened stores.
Given an input array A, your goal is to decide which stores to open, choosing among the values of i for which A[i] = 1. The only condition you must meet is that each pair of stores must be separated by at least three blocks. In other words, if you open stores on blocks x and y, then y − x ≥ 3.
Your goal is to open as many stores as possible.
For example, if n = 16 and A = [0,1,0,1,0,1,0,1,0,1,0,1,1,0,0,0], then the optimal solution is to
open stores on blocks i = 2, 6, 10, 13, as illustrated in bold:
A = [0,1,0,1,0,1,0,1,0,1,0,1,1,0,0,0].
Provide a greedy
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
