# Questions tagged [greedy-algorithms]

Questions about algorithms that make at each step the locally optimal choice.

349 questions
Filter by
Sorted by
Tagged with
791 views

### How to understand the solution to Task Scheduler problem on LeetCode?

LeetCode Task Scheduler problem is the following: Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any ...
44 views

### Serving $k$ customers with bounded time window

A person provides a service and he/she can serve $k$ clients each minute. Now, client number $i$ comes at the beginning of minute $a_{i}$ and waits $w_{i}$ minutes to receive the service and if they ...
45 views

### Ordering the tasks to minimize penalties

So I just started learning greedy algorithms and I have a problem that I want to solve. The statement is as follows: In your calendar you have an $L$ list of all the tasks you need to complete today. ...
86 views

### Correctness proof of a greedy approximation algorithm

How do I prove the correctness of this algorithm?
51 views

### Maximize the minimum gap while scheduling within intervals?

Problem There are N intervals in which a particular integer can be chosen. What is the maximum possible minimum gap between each integer if one integer is chosen for each of those intervals? For ...
83 views

### Why this problem has such a simple solution? How would you avoid looking for more complex solutions first?

There's a problem whose solution startles me because at first sigh, I wouldn't imagine that it could be solved so easily. The problem is: There are n tasks, each task ...
41 views

### Mathematical expression for the quantity that we are maximising in the stock buying and selling problem

Problem Statement: Say you have an array prices for which the $i^{th}$ element is the price of a given stock on day $i$. Design an algorithm to find the maximum profit. You may complete as many ...
79 views

### What is an algorithm for minimizing the standard deviation of m sums summed from n summands? [with attempt]

I have m bins (sums) and n summands. Each summand goes into a bin. In order to minimize the standard deviation, I have a greedy algorithm that appears to accomplish this. I am not sure of the name, ...
53 views

### Prove following statement about Kruskal Algorithm

Let G be undirected graph, G=(V,E), and all edge weights are distinct. Consider an edge e=(u,v)∈E that wasn't included in the solution obtained from applying Kruskal Algorithm to G. Prove that this ...
51 views

### Find the maximum number of valid cartesian coordinates

Given a list X containing m number of x coordinates and a list Y containing m number of y coordinates. The coordinate (x, y) is valid if and only if the difference between x and y is less than or ...
40 views

### Choosing a method for algorithmic problems - is it an art or science?

I've been doing lot of programming challenges lately (such as on leetcode.com) and often find myself in a situation when I cannot pick a method for solving a problem. I stuck with questions like - ...
19 views

### Minimizing the length a Boolean Algebra Expression in disjunctive normal form

I'm looking to minimize the length of an expression in boolean algebra that has been given in disjunctive normal form and is free from redundancy. To remove redundancy from the original expression I ...
89 views

### Binary string satisfying several constraints

I'm trying to solve this problem, but without success. Problem: You're given a binary string where some of the bits are replaced by ?. You're also given several ...
48 views

### Algorithm for summation with lowest maximum temporary sum

I've got this problem on my last exam, which I struggle to deal with. Let's say we have array of $N$ integers (it can be float too, but let's say integers for sake of simplicity. We need to sum those ...
248 views

### Difficulty in understanding the proof of the lemma : “Matroids exhibit the optimal-substructure property”

I was going through the text "Introduction to Algorithms" by Cormen et. al. where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma ...
543 views

We have N tasks that need to be scheduled for processing. Each task consists of two parts that need to executed in order. The first one is guarded by a mutex and ...
23 views

### An independent d-division

I would love to have a direction for the following exercise (the material for this exercise is greedy algorithms): Let $G = (V,E)$ an undirected graph whose vertices $V = \{v_1,\dots,v_n\}$ appear in ...
185 views

### Negative cycle detection using Bellman-Ford and its correctness

I recently started studying algorithms on my own using Cormen and MIT algo videos in YouTube. I am going thru Bellman-Ford. I have 2 doubts about the correctness of the algorithm: Why are we ...
207 views

### Using a greedy algorithm to find a cut S which at least half of the edges cut

Let $G$ be an undirected graph. Find a greedy algorithm that finds a cut $S$ which at least half of the edges cut. I tried to think about something like choosing the vertex with the highest degree, ...
58 views

### Scheduling algorithm for overlapping jobs - single resource?

I have a single resource that will need to shared for running multiple parallel jobs. Think of the resource as a straight line numbered from 1 to 100. The jobs occupy part of the line while they are ...
63 views

### Three City Scheduling

I came across the following interview question There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-...
28 views

### Remove vertices to get k-connected components

In a graph, I need to remove some vertices in order to get at least k-connected components. The no. of removed vertices should be low. Is there a heuristic that I could follow for this?
32 views

### Does this problem have a formal name?

I have come across the following problem but am unable to understand the solution for it. Hence I would like to know if it has a formal name then, I can search for it and read about it in more detail. ...
52 views

### Problem related to set partitioning

Let $A_j=\{(a^i_j,b^i_j)~:~ 0 \leq i \leq n,\text{and } a^i_j,b^i_j \in \mathbb{Z}^+\}$ Given sets $A_1,\ldots, A_{p}$ and a positive integer $k$, the problem is to check whether there exists one ...
167 views

### Minimum steps to sort array [closed]

Consider you have a permutation of $1$ to $n$ in an array $array$. Now select three distinct indices $i$,$j$,$k$, there is no need to be sorted. Let $array_i$, $array_j$ and $array_k$ be the values ...
143 views

### Proof of a greedy algorithm used for a variation of bin-packing problem

We are given an array of weights $W$ (all weights are positive integers), and we need to put the weights inside bins. Each bin can hold a maximum of Max_val, and each weight is at most Max_val. The ...
23 views

### How proof of Hoffman algorithm greedy property starts with optimal tree T?

In this paper Claim 1 states that x and y are smallest probability and there is optimal code tree in which this two characters are siblings at the maximum depth. In proof to that claim, author starts ...
204 views

### Greedy algorithm to divide objects into the lowest number of groups of a maximum size

I have n objects of independent size s, and need to group them so that the sum of the sizes of each group is smaller than a given maximum size, and the number of groups is the smallest possible. I ...
457 views

### N numbers, N/2 pairs. Minimizing the maximum sum of a pairing. Proving greedy algorithm

So say I have n numbers, where n is even. I want to pair the numbers such that the maximum sum of the pairs is minimized. For example -2, 3, 4, 5. The ideal pairing is (-2, 5), (3, 4), since its ...
85 views

775 views

### Gas Station Problem - Dijkstra's Algorithm variation

I am trying to find an algorithm which finds the least expensive route from one town to another. This is the general setup. There are a series of one-way roads from some towns to other towns. Not ...
127 views

### center selection problem: Simple greedy algorithm

I am trying to understand the following text which defines a greedy algorithm for center selection problem: It would put the first center at the best possible location for a single center, then ...