判断题：Revisit the activity selection problem. Given a set of activitie

Revisit the activity selection problem. Given a set of activities $S=\{a_1, a_2, \cdots, a_n \}$ that wish to use a resource, each $a_i$ takes place during a time interval. The goal is to arrange as many compatible activities as possible. Recall that several greedy approaches are introduced in the class, among which the one selecting an activity with the shortest length, denoted by $SF$, is not always optimal. However, we claim that $$SF$$ accepts at least $|OPT|/2$ activities, given that the optimal value is $|OPT|$, where $OPT$ is an optimal solution. Check if the following is a correct proof. 

We use a technique, called the charging scheme, similarly as the amortized analysis. Suppose each accepted activity of $$OPT$$ holds one dollar, which will be given to the activities accepted by $SF$ in the following way. For any activity $a_i$ of $OPT$, if $a_i$ is also accepted by $SF$, give the dolloar to itself. Otherwise, there must be some activity $a_j$, accepted by $SF$, is not compatible with $a_i$. Then $a_j$ receives one dollar from $a_i$. Along this line, each activity of $OPT$ sends out one dollar to an activity in $SF$, while each activity of $SF$ receives at most two dollars. It implies that $SF$ accepts as least $|OPT|/2$ activities.

 

答案：TRUE