Many people on different articles suggests that if an optimization problem has a greedy solution, the underlying structure must have matroid property.
I was trying to understand this. So far, I was able to prove that for,
1. Maximum sum of m integers among n integer.
2. Minimum spanning tree.
However, The classical greedy algorithm Activity Selection seems to fail having exchange property.
Let,E = {1-3, 2-4, 3-5, 4-6, 5-7}
Now, Take two independent set,I = {2-4, 4-6}
and J = {1-3, 3-5, 5-7}
There is no activity in J
which can extend I
. Which fails the exchange property of matroid, if I understood it correctly. Thus, it is not matroid and shouldn't have a greedy algorithms.
Where am I wrong?
NB:
1. a-b means starts at time a end just before time b.
2. I know matroid is not best way to find greedy algorithms in contest. I just like to understand the underlying structure once.
EDIT:
Please Suggest some math forum where I may get the answer.