Reorganizing bus frequencies to cater for actual travel demands can signicantly save the cost of the public transport system. This paper studies the bus frequency optimization problem considering the user satisfaction. Specically, for the first time to our best knowledge, we study how to schedule the buses such that the total number of passengers who could receive their bus services within the waiting time threshold can be maximized. We propose two variants of the problem, FAST and FASTCO, to cater for different application needs and prove that both are NP-hard… Experiments on a real city-wide bus dataset in Singapore have been conducted to verify the efciency, effectiveness, and scalability of our methods in addressing FAST and FASTCO.