Задача о покрытии набора точек отрезками равной длины

Существует классическая задача о покрытии точек отрезками - на числовой оси находятся n целочисленных точек и задача просит найти минимальное количество отрезков указанной длины способных покрыть все точки. Точка считается покрытой если находится на границе отрезка. Например, нам даны пять точек с координатами {1, 2, 3, 4, 5} и отрезки единичной длины - для такого набора ответ на задачу будет 3, тк все точки можно покрыть 3 отрезками [1,2], [3,4], [4,5], двумя отрезками этого не выйдет. Такая задача легко решается жадным алгоритмом.

int Cover(std::vector<int>& data, int l) {
//сортируем вектор координат точек
    std::sort(data.begin(), data.end());
    

    int interval_count = 1; // количество отрезков
    int r_point = data[0] + l; //правая граница последнего установленного отрезка
    for(int& elem : data){
        if(elem > r_point){
            interval_count += 1;
            r_point = elem + l;
        }
    }
    
    return interval_count;
}

Так вот меня интересует обратная задача - найти минимальную длину отрезков, когда по условию дан набор точек и количество отрезков. На самом деле ничего лучше перебора разных длин я не придумал :( Своё решение я построил на основе бинарного поиска по длинам в диапазоне (0, data.back() - data.front()). Каждая длина в поиске ставится в проверку - покроют ли k отрезков (по условию) длиной l набор точек data (переделанное решение классической задачи.

bool CanCover(const std::vector<int>& data, int l, int k){
    
    --k;
    int r_point = data[0] + l;
    
    for(const int& elem : data){
        if(elem > r_point){
            --k;
            r_point = elem + l;
            if (k < 0) return false;
        }
    }
    
    return true;
}

Вот сам бинарный поиск

int Binary(std::vector<int>& data, int k){
    if(k >= data.size()) return 0; //если отрезков больше чем точек, то отрезки могут быть длиной 0 и лежать на каждой из точек
    
    std::sort(data.begin(), data.end());
    
    //границы поиска
    int left = 0;
    int right = data.back() - data.front();
    
    while(left < right){
            int mid = (left + right) / 2;
            
            if(CanCover(data, mid, k)) right = mid;
            else left = mid + 1;
    }
    
    return left;
}

Но как выяснилось в результате тестов, решение через бинарный поиск недостаточно быстрое. Может есть способ как найти минимальную длину отрезков без прохода по всем длинам? Что-нибудь наподобие жадного алгоритма, как для классической задачи?