Emerging　applications　impose　the　min-max　line　barrier　coverage　(LBC)　problem　that　aims　to　minimize　the　maximum　movement　of　the　sensors　for　the　sake　of　balancing　energy　consumption.　In　the　paper,　we　devise　an　algorithm　for　LBC　that　finds　an　optimal　solution　within　a　runtime　$O(n^{2})$,　improving　the　previous　state-of-art　runtime　$o(n^{2}\log　n)$　due　to　[7].　The　key　idea　to　accelerating　the　computation　of　the　optimum　solutions　is　to　use　approximation　solutions　that　are　obtained　by　our　devised　approximation　algorithm.　Numerical　experiments　demonstrate　our　algorithms　outperform　all　the　other　baselines　including　the　previous　state-of-art　algorithm.　©　2021　IEEE.