# Questions tagged [greedy-algorithms]

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

342 questions
Filter by
Sorted by
Tagged with
192 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, ...
98 views

6k views

### How does “Greedy Stays Ahead” Prove an Optimal Greedy Algorithm?

I have found many proofs online about proving that a greedy algorithm is optimal, specifically within the context of the interval scheduling problem. On the second page of Cornell's Greedy Stays ...
2k views

### Relation between the “Point-Cover-Interval” problem and the “Interval Scheduling” problem

Point-Cover-Interval Problem: Given a set $\mathcal{I}$ of $n$ intervals $[s_1, f_1], \ldots, [s_n, f_n]$ along a real line, find a minimum number of points $P$ such that each interval contains some ...
804 views

### Find the minimum set of intervals for given set of numbers

For any given set of real numbers, find the minimum set of intervals with length 1 that include all elements. For example, for the set: $${\{1.5,2.3,2.4,2.5,2.8,3.3,3.6,3.8}\}$$ the answer is {\{[1....
1k views

### How to prove a greedy algorithm that uses the longest increasing subsequence?

Here is the thing, I am solving an problem, and I think, say, I am pretty sure that I have the correct algorithm but I haven't been able to prove it because of my lack of practice prooving greedy ...