Carvans Solution

Problem You’re given the maximum speed of N cars in the order they entered the long straight segment of the circuit. Each car prefers to move at its maximum speed. If that’s not possible because of the front car being slow, it might have to lower its speed. It still moves […]

Ciel and Receipt Solution

ProblemTomya is a girl. She loves Chef Ciel very much. Tomya like a positive integer p, and now she wants to get a receipt of Ciel’s restaurant whose total price is exactly p. Note that the i-th menu has the price 2i-1 (1 ≤ i ≤ 12). Find the minimum number of menus whose total price is […]

Activity Selection problem

Activity selection problem is the problem of selecting the largest set of mutually exclusive activities. Problem Statement Let S = {1, 2, …n} be the set of activities that compete for a resource. Each activity has its own starting time and finish time . If selected activity takes place during time […]

Custom Sort String – LeetCode Solution [Medium]

Problem statement You are given two strings order and s. All the words of order are unique and were sorted in some custom order previously. Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string. Return any permutation of s that satisfies this […]

Job sequencing problem

Problem statement There are n jobs to be processed on a machine. Each job i has a deadline and profit >= 0. is earned if the job is completed by its deadline. Job is completed if it is processed on a machine for unit time. Only one job is processed at […]

Greedy approach vs Dynamic Programming

Greedy approach and Dynamic programming both are used for solving optimisation problems. However often we need to use DP since optimal solution cannot be guaranteed by a greedy algorithm. Consider Knapsack problem We could solve it by brute-force, by generating all possibilities of choosing a subset of n items and selecting […]