Effective video inpainting that maintains both temporal and spatial continuity is required in many applications. This research presents a new video inpainting algorithm targeted at achieving a better tradeoff between visual quality and computational complexity. The inpainting regions in video frames are classified into two types, i.e., structure and smooth. A scheduling mechanism considering texture data amount, inpainting confidence and motion vector uniformity is proposed to determine an appropriate processing order of inpainting points. A novel patch comparison function to evaluate the similarity and an irregular patch-filling method are developed to ensure decent visual quality and faster inpainting speed. The ideas of multi-resolution processing and scale-invariant feature transform are further adopted such that larger inpainting areas can still be processed well. To evaluate the effectiveness of the proposed algorithm, inpainting on television programs and video clips from literature is tested. The experimental results demonstrate better performance when compared with traditional methods.