Video caching has gained significant attention due to its cost efficiency. In this paper, we propose an optimized cache replacement scheme based on the user request arrival pattern. The users are grouped among all possible request intervals, and the user density is calculated in each interval. The groups with highest user density are cached. Whenever a group with high user density arrives, the groups with lower density will be replaced. The simulation results show that the proposed schemes can double the hit ratio compared with the Least recently Used (LRU) scheme.