PROBLEM LINK:
Author: TSEC CodeCell
DIFFICULTY:
Easy
PROBLEM:
Given a collection of N rods of different lengths L, find the minimum cost to buy all rods if it costs one unit to buy all rods in the range [L,L+6].
EXPLANATION:
Sort rods in a non decreasing order based on length and then iterate through them. Increase cost by one for each rod encountered with length L and then skip any rods with lengths in the range [L,L+6]. The solution employs a simple greedy strategy. If a rod is present of length L, we can immediately skip all rods in the range [L,L+6] and increase cost by only one. Using this technique we can find the optimal cost in O(n) time.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.