Questions tagged [greedy-algorithms]

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

Filter by
Sorted by
Tagged with
1 vote
1 answer
48 views

Formal Proof on why Greedy isn't working on one Particular Problem

Problem You are given two integer arrays nums and multipliers of size n and ...
user avatar
0 votes
0 answers
19 views

Is this how Interval Partitioning Problem aka interval graph coloring problem works?

You can refer the problem on later part of section 4.1 in "Algorithm Design Book by Jon Kleinberg and Éva Tardos" Problem: We have "n" lectures and we our job is to assign all of ...
user avatar
0 votes
2 answers
85 views

Maximum subarray sum of given length range

Can anyone please help me solve this better than $O(|a-b| \cdot n)$? Given an array of both negative and positive numbers, we want to find the maximum sum of the elements in contiguous subarray having ...
user avatar
  • 35
-1 votes
1 answer
63 views

Largest number of disjoint paths of length $k$ and maximum reward in a tree

Consider exercise 23(c) of chapter "Greedy Algorithms", Algorithms by Jeff Erickson. Given a tree $T=(V,E)$ in which each node has a reward, and $k\in\mathbb{N}$, our goal is to find a set $...
user avatar
  • 1
0 votes
1 answer
29 views

Greedy algorithm for postive interval covering

Consider this problem from Jeff Erickson Algorithm that already in this site, there is a this post about it where it want us prove a lower bound for it. The question is: Suppose you are given an ...
user avatar
  • 1
0 votes
1 answer
33 views

Tweaking Floyd-Warshall Algorithm to detect cycles

Cheers, I am trying to solve the problem of minimum length cycle in a graph, and I came across a solution that suggested that I should tweak the Floyd-Warshall algorithm to solve that. It stated that ...
user avatar
0 votes
1 answer
95 views

Find largest number of disjoint paths with lenght $k$ in a tree

Consider this problem from Jeff book Given a rooted tree $T$ and an integer $k$ as input, and it should compute the largest possible number of disjoint paths in $T$ , where each path has length $k$. ...
user avatar
  • 1
2 votes
1 answer
73 views

Prove a greedy algorithm that obtains the minimum integer with at most k adjacent swaps is correct

This problem is from LeetCode. You're given a string num representing the digits of a very large integer and an integer k. You are allowed to swap any two adjacent digits of the integer at most k ...
user avatar
0 votes
0 answers
68 views

Is this greedy algorithm optimal?

Let $T=(V,E)$ be a tree and let $k$ be a natural number. The problem is to find the largest set of vertices $S \subseteq V$ such that $(*)$ every path in $T$ consists of at most $k$ vertices from $S$. ...
user avatar
  • 13
3 votes
1 answer
148 views

Greedy filling unit intervals

I have unit intervals given such as $I = \{\{s_1, s_1 + 1\}, ..., \{s_k, s_k+1\}\}$ ($\forall s_i \in \mathbb{R}$). I am given a list of $X$ reals, such that each of the reals belongs to at least one ...
user avatar
  • 149
2 votes
1 answer
72 views

Does this greedy algorithm minimize the sum of the diameters of two clusters?

Suppose given $2n$ points in the plane and we want to partition points into two clusters $C_1$ , $C_2$ such that each cluster contains exactly $n$ points and we want to minimize the sum of the ...
user avatar
  • 1
1 vote
0 answers
34 views

Proving the least number of operators required equals $min((x-target)*2, (target*2)-1)$

Here is the source for the problem below: https://leetcode.com/problems/least-operators-to-express-number/discuss/1675169/java-or-recursion-or-greedy-or-math For completeness, below is the problem ...
user avatar
0 votes
1 answer
76 views

Is there a solution faster than O(n^2) for this greedy/sorting problem?

In a market there are N different items where each item is unique and identified by id (1-N). There are also K buyers with names (1-K). Each buyer has 2 items that they want to buy (A, B), where A is ...
user avatar
  • 21
1 vote
2 answers
191 views

finding a greedy algorithm that maximizes total energy of fruits subject to expiry dates

This problem is based off of the following problem on stack overflow: https://stackoverflow.com/questions/64797299/greedy-algorithm-to-maximize-score. The second answer is incorrect because the ...
user avatar
4 votes
1 answer
137 views

Parition a multiset of numbers into two subsets, how to maximize the sum of their medians?

Given a multiset $S$ of numbers, partition it into two subsets $S_1 $ and $S_2$. How to maximize the sum of their medians? For example, the median of {1,2} is ...
user avatar
  • 177
1 vote
0 answers
65 views

Graph in which greedy algorithm for maximum matching is a 2-approximation

Here is a greedy algorithm for maximum bipartite matching: Iteratively select an edge that is not incident to previously selected edges. This algorithm returns a 2-approximation, and runs in linear ...
user avatar
  • 111
0 votes
0 answers
30 views

Find set of vertices of max size under some restrictions [duplicate]

I've faced a problem and I don't know what approach I must follow, dynamic programming or greedy method, so here is the question. Question: Given a directed tree $T=(V,\ E)$. We're required to find a ...
user avatar
0 votes
1 answer
81 views

Find most vertices in a directed tree where no path of length less than 3 connects any pair

Given a directed tree $T = (V, E)$, we need to find a set of vertices $A \subseteq V$ such that for every two vertices $v,u \in A$ either there is no path between them or the path between them is of ...
user avatar
1 vote
0 answers
64 views

Is the optimal substructure property necessary to guarantee the existence of a greedy algorithm that always finds the optimal result?

I'm trying to understand what is necessary to guarantee that a problem has a greedy algorithm that always produces optimal solutions. In multiple places I find that a greedy algorithm can be ...
user avatar
1 vote
1 answer
38 views

Where does each part of the $1 - (1 - 1/k)^k$ approximation for the Maximum Coverage problem come from?

A solution to an instance of the Maximum Coverage problem with a budget of k subsets can be approximated with a greedy algorithm that, at each iteration, picks one of the subsets that adds the most ...
user avatar
2 votes
1 answer
211 views

Greedy Stays Ahead proof of "Jump Game"

(Source: https://leetcode.com/problems/jump-game-ii/) Consider the following problem: Given an array of non-negative integers nums, you are initially positioned at the first index of the array. Each ...
user avatar
  • 151
2 votes
1 answer
34 views

Optimal order to minimise time until first success

Say you are a salesperson and you want to make a sale; there are $N$ customers on your list; customer $i$ takes $t_i$ time to talk to and there is $p_i$ probability to make the sale to that customer - ...
user avatar
  • 23
5 votes
0 answers
116 views

discrete optimization problem with a matrix inverse

I'm trying to solve this discrete optimization problem:$\newcommand{\I}{\mathcal{I}}\newcommand{\R}{\mathbb{R}}$ $$\max_{|\I| \le k} f(\I) \qquad\text{where}\; f(\I) :=x_{\I}^{\top} (\Sigma_{\I})^{-1} ...
user avatar
0 votes
1 answer
79 views

Maximum number of teams that can be formed with given age such that the sum of their age is more than 18

An array of students age is given : $ A = \{ A_1,A_2, ..., A_n \} $. Form maximum number of teams such that the sum of age for each team is more than 18. Note that each team consists of only 2 people. ...
user avatar
2 votes
2 answers
114 views

Given n positive integers, pick two elements and subtract each by one with one operation. Find max operations

Problem Description: we have an array of n positive integers and in one operation we have to choose two elements in the array and decrease them by 1. (Elements on which we are performing this ...
user avatar
  • 21
0 votes
0 answers
30 views

Why can we solve this problem by a greedy algorithm?

https://atcoder.jp/contests/past202004-open/tasks/past202004_f I am trying to solve the following problem: We have $N$ tasks. Let today be Day $1$. You can do the $i$-th task on or after Day $A_i$, ...
user avatar
3 votes
2 answers
196 views

Algorithm that finds a matrix with a specific number of 1s in its rows & columns

Question: Given integer $n \geq 2$ and two lists of size $n$, $A$ and $B$, of non-negative integers, determine if there exists an $n \times n$ matrix whose $i$-th row has $A[i]$ $1$s and whose $j$-th ...
user avatar
2 votes
1 answer
79 views

Determines the smallest set of unit-length closed intervals that contains all of the given points

Question: Describe an efficient algorithm that, given a set $\{x1, \cdots, x_n\}$ of points on the real line, determines the smallest set of unit-length closed intervals that contains all of the given ...
user avatar
  • 459
1 vote
1 answer
42 views

The preliminary of the Bandit Gradient Algorithm

In the papers introducing The Bandit Gradient Algorithm as Stochastic Gradient Ascent, the following relationship: is always considered as a preliminary and lacks proof for it. Does anyone know how ...
user avatar
0 votes
0 answers
58 views

Optimal Word Guessing Algorithm in $O(n \log n)$

Say that your friend picks a word $(w_1, w_2,\dots,w_n)$ according to a known probability distribution $(p_1,p_2,\dots,p_n)$. You ask yes or no questions until you are certain which word has been ...
user avatar
  • 13
1 vote
0 answers
29 views

Social Networking Disease Transmission

You are given an undirected graph (social network) in which each edge $e = (v, v')$ has an interval $I_e = [l_e, u_e]$ on it. The meaning is that you know that $v$ and $v'$ met at some point during ...
user avatar
0 votes
1 answer
58 views

Bin packing problem and optimality proof

Let $W$ be an array of weights. Store all the weights of $W$ in bins such that in each bin a heavier weight always go before a lighter weight (if $w_i\in W$ is stored before $w_j\in W$ then ...
user avatar
  • 115
0 votes
1 answer
110 views

Time-varying edge cost Minimum Spaning Tree

I am having a hard time wrapping my head around the time-varying edge cost of this question : Suppose we have a connected graph $G = (V, E)$. Each edge e now has a time-varying edge cost given by a ...
user avatar
2 votes
1 answer
54 views

Why is this greedy strategy always correct for this problem?

I'm trying to solve the following problem: https://cses.fi/problemset/task/1084/ My first idea to solve this was to sort the applicants and apartments in increasing order. Then, I iterate through all ...
user avatar
  • 123
0 votes
1 answer
58 views

Greedy approach behind SPOJ Aggressive Cows problem

My doubt is related to the given SPOJ problem: Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 &...
user avatar
0 votes
0 answers
75 views

Gas Station problem proof

I'm trying to prove the solution for the problem Gas Station (LeetCode 134) Let's define $d_i$ to be the difference $g_i - c_i$. Basically it's a greedy solution where you look for the first $k$ s.t. $...
user avatar
0 votes
0 answers
73 views

Sequential Tasks with Greedy Algorithm

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 therefore only one task can be ...
user avatar
0 votes
0 answers
116 views

A Variant to "Boats to Save People"

This question is a variant of LeetCode 881. Boats to Save People by removing the restriction of "each boat carries at most two people at the same time" from the original question. Problem ...
user avatar
  • 1,071
-1 votes
1 answer
54 views

Proving correctness for greedy algorithm in string removal problem

Problem Statement: You are given a string s and two integers x and y. You can perform two types of operations any number of times. Remove substring "ab" and gain x points. For example, when ...
user avatar
  • 39
0 votes
0 answers
35 views

Sum optimization and greedy approach

I've came across the optimization bellow $\phi=argmin_{\theta} \displaystyle\sum_{i=1}^{N}f(x_i,\theta)$ Can i say that minimizing this summation by minimizing each term $\left(\displaystyle\frac{df(...
user avatar
0 votes
1 answer
216 views

How to determine the approximation factor for greedy vertex cover algorithm?

The algorithm iteratively picks the vertex with maximum degree and removes it and every incident edge of the vertex, until only vertices with degree of $0$ are left. Formally: $\text{GreedyVertexCover}...
user avatar
7 votes
0 answers
91 views

Optimality of DSATUR on interval graphs

The DSATUR algorithm is a greedy graph coloring algorithm. It consists of applying the usual greedy coloring algorithm, considering vertices in reverse lexicographic order of (number of different ...
user avatar
  • 6,942
1 vote
1 answer
249 views

Minimal number of intervals that covers $\{1,...,k\}$

Let $F$ be a family of sets of consecutive integers in $\{1,…,k\}$ that is closed under taking subintervals, i.e. for any $a≤b≤c≤d$, if $\{a,…,d\} \in F$, then $\{b,…,c\} \in F$ also. Find a minimum ...
user avatar
3 votes
0 answers
39 views

Equalizing level of water in glasses problem

I have a problem on my hands, and would like help matching it to the existing, studied problems. I explain it like so: I have a sequence of $n$ equal-sized glasses of water. Each has a different ...
user avatar
-1 votes
1 answer
42 views

Fitting arrays into RAM algorithm question

We'll consider the RAM as a sequence of cells that can contain data. Some cells already contain some data, some are empty. The empty cells form the so-called memory clusters. Thus, a memory cluster is ...
user avatar
  • 143
3 votes
1 answer
142 views

Partition of a $k$-partite graph to minimal number of connected sets

Let $G$ be a $k$-partite directed acyclic graph where the edges are only between two adjacent sets of vertices. I'm trying to partition the graph to the minimal number of connected sets. Sets $A_0, ...
user avatar
1 vote
0 answers
55 views

Finding an optimal solution for the following problem

This is an intriguing question given by my friend for which I want to find an optimal solution: Each week, you can choose to work ONLINE $(ON)$ or in person $(WR)$ in your department's office. If you ...
user avatar
  • 341
0 votes
0 answers
426 views

Minimum Number of Refueling Stops with Dynamic Programming

This is a question from Leetcode and I wanted to solve it with Dynamic Programming. upon seeing the solution, I am not able to get the intuition behind the logic. I was able to understand the solution ...
user avatar
  • 159
1 vote
0 answers
21 views

Time to form a complete graph from n vertices given that only k vertices can be used at a time [closed]

I know this problem is related to the greedy algorithm and max edges incomplete graph but can't come up with a solution. Problem You are given two numbers n and k: n >= k n is the total # of ...
user avatar
0 votes
1 answer
154 views

How to prove the my greedy algorithm for placing guards?

Given $n$ images placed in indexes $x_1 < x_2 < ... < x_n$ and an endless number of guards, where each guard if placed in index $y$ can protect $[y-0.5,y+1]$. I want to protect all images ...
user avatar
  • 13

1
2 3 4 5
8