Emerging　applications　raise　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　this　paper,　we　devise　an　exact　algorithm　to　optimally　solve　LBC　within　a　runtime　of　O(n2),　comparing　favorably　to　the　previous　state-of-art　runtime　O(n2　logn),　where　n　is　the　number　of　sensors.　To　achieve　the　improvement,　we　accelerate　the　computation　of　optimum　solutions　by　using　a　novel　approximation　algorithm.　Numerical　experiments　demonstrated　that　our　algorithms　outperform　all　the　other　baselines,　including　the　previous　state-of-art　algorithm.　©　2021　ACM.