Given the cost of painting different intervals of a wall, find the minimum cost of painting the entire wall.
Java Program
package com.sourabh.first; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class OptimisedPainting { public static void main(String[] args) { Interval paintInterval = new Interval(); paintInterval.setStart(0); paintInterval.setEnd(5); Map<Interval, Integer> unitHashMap = new HashMap<>(); for(int i=paintInterval.getStart(); i<paintInterval.getEnd(); i++) { Interval interval = new Interval(); interval.setStart(i); interval.setEnd(i+1); unitHashMap.put(interval, 0); } //String intervalString = "[0, 5, 10], [0, 4, 1], [0, 2, 5], [2, 5, 1]"; String intervalString = "[1, 4, 10], [2, 5, 6]"; String[] intervals = intervalString.split("],"); List<Interval> intervalsList = new ArrayList<>(); for(int i=0;i<intervals.length;i++) { String[] parts = intervals[i].split(","); Interval interval = new Interval(); interval.setStart(Integer.parseInt(parts[0].trim().substring(1))); interval.setEnd(Integer.parseInt(parts[1].trim().replaceAll(",", ""))); interval.setCost(Double.parseDouble(parts[2].trim().replaceAll("]", ""))); intervalsList.add(interval); } System.out.println("Input"); for(Interval combination : intervalsList) { System.out.println(combination.getStart() + "," + combination.getEnd() + "," + combination.getCost()); } System.out.println("Output"); OptimisedPainting op = new OptimisedPainting(); List<List<Interval>> intervalsCombinations = op.generateCombinations(intervalsList, new ArrayList<>(), 0, new ArrayList<>()); Double minCost = 999999.99; for(List<Interval> intervalsCombination : intervalsCombinations) { Double cost = 0.0; if(op.isValidIntervalList(intervalsCombination, unitHashMap)) { for(Interval combination : intervalsCombination) { cost += combination.getCost(); } if(minCost > cost) { minCost = cost; } } unitHashMap = op.refreshUnitHashMap(paintInterval); } if(minCost == 999999.99) { System.out.println("-1"); } else { System.out.println("Minimum cost: " + minCost); } } public Map<Interval, Integer> refreshUnitHashMap(Interval paintInterval) { Map<Interval, Integer> unitHashMap = new HashMap<>(); for(int i=paintInterval.getStart(); i<paintInterval.getEnd(); i++) { Interval interval = new Interval(); interval.setStart(i); interval.setEnd(i+1); unitHashMap.put(interval, 0); } return unitHashMap; } public boolean isValidIntervalList(List<Interval> intervalsList, Map<Interval, Integer> unitHashMap) { for(Interval interval : intervalsList) { for(int i=interval.getStart(); i<interval.getEnd(); i++) { Interval temp = new Interval(); temp.setStart(i); temp.setEnd(i+1); unitHashMap.put(temp, 1); } } return !unitHashMap.containsValue(0); } public List<List<Interval>> generateCombinations(List<Interval> intervalsList, List<List<Interval>> intervalsCombinations, int start, List<Interval> outputList) { for(int index = start; index < intervalsList.size(); index++) { outputList.add(intervalsList.get(index)); List<Interval> tempList = new ArrayList<>(); for(Interval interval : outputList) { tempList.add(interval); } intervalsCombinations.add(tempList); tempList = null; intervalsCombinations = generateCombinations(intervalsList, intervalsCombinations, index+1, outputList); outputList.remove(outputList.size() - 1); } return intervalsCombinations; } } class Interval { private int start; private int end; private double cost; public int getStart() { return start; } public void setStart(int start) { this.start = start; } public int getEnd() { return end; } public void setEnd(int end) { this.end = end; } public double getCost() { return cost; } public void setCost(double cost) { this.cost = cost; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + end; result = prime * result + start; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Interval other = (Interval) obj; if (end != other.end) return false; if (start != other.start) return false; return true; } }