# Questions tagged [greedy-algorithms]

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

58 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k views

### What algorithm does OLA and UBER use for allotting taxis

More specifically : lets say i have 5 taxis , each available for booking at t=0; i have two days (48 hrs) with me how can I maximise their booking . I may not be able to clarify the question , this ...
367 views

### Interval scheduling, unclear greedy proof

I am having trouble understanding the proof of the theorem, which states that the greedy scheduling algorithm produces solutions of maximum size for the scheduling problem. The proof that I am ...
70 views

### Planning interviews

This is real-world problem, but I need to model it with algorithm as I am going to implement it (probably with PostGIS and Google Maps). Problem is: Everyday I am receiving job offers, and I have to ...
181 views

### Greedy algorithm correctness proof (UVA 10716)

Given an input string, not necessarily a palindrome, compute the number of swaps necessary to transform the string into a palindrome. By swap we mean reversing the order of two adjacent symbols (UVA ...
55 views

### How can I divide a set of strings into subsets of fixed size with maximal homogeneity?

Suppose I have a set of 1000 binary strings of fixed length. I wish to divide these 1000 strings into 10 subsets of 100 strings each, in such a way that the subsets are maximally homogeneous. I want ...
49 views

### Approximate algorithm to find the minimum score

Given $n$ variables and a function $f$ such that $f(v) = N(v) + D(v)$, where $N$ and $D$ are the subfunctions of function $f$. Function $f$, can be considered as an oracle. Query: let $v \in P$, ...