[HELP] What is the proof of this greedy solution ?

Revision en1, by abcdqwerty12345, 2021-11-08 01:53:52

Problem

Basically you are given an array and you have to keep removing any two unequal elements until the size of the array is minumum.

In the editorial it's said:- We get the following greedy solution — each time we take two characters with maximal occurrences number and delete them.

Can anyone plz tell why this solution always give the optimal answer ? Like why everytime we are selecting the elements with maximum frequency?

Thx a lot !!!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English abcdqwerty12345 2021-11-08 01:53:52 558 Initial revision (published)