Problem: We will play a one-player game using a number line and N pieces.  First, we place each of these pieces at some integer coordinate.  Here, multiple pieces can be placed at the same coordinate.  Our objective is to visit all of the M coordinates X_1, X_2, ..., X_M with these pieces, by repeating the following move:  **Move** : Choose a piece and let x be its coordinate. Put that piece at coordinate x+1 or x-1.  Note that the coordinates where we initially place the pieces are already regarded as visited.  Find the minimum number of moves required to achieve the objective.

Submission attempts (in order):
import math
import sys


def solution(arr, moves):
    if len(arr) <= moves:
        return 0

    arr.sort()
    if moves == 1:
        return abs(arr[0] - arr[-1])

    diff = [None] * len(arr)
    diff[0] = abs(arr[0] - arr[1])
    diff[-1] = abs(arr[-2] - arr[-1])
    for i in range(1, len(arr) - 1):
        diff[i] = abs(arr[i] - arr[i - 1]) if  abs(arr[i] - arr[i - 1]) > abs(arr[i] - arr[i + 1]) else abs(arr[i] - arr[i + 1])
    d = enumerate(diff)

    visited = {}
    current_positions = {}

    for i in list(reversed(sorted(d, key=lambda x: x[1])))[:moves]:
        visited[i[0]] = True
        current_positions[i[0]] = True

    counter = 0
    while len(visited) < len(arr):
        min_on_position = sys.maxsize
        minimum_element = None
        side = None
        for i in current_positions:
            if i - 1 not in visited and i > 0:
                if min_on_position > abs(arr[i - 1] - arr[i]):
                    min_on_position = abs(arr[i - 1] - arr[i])
                    minimum_element = i
                    side = i - 1

            if i + 1 not in visited and i < len(arr) - 1:
                if min_on_position > abs(arr[i + 1] - arr[i]):
                    min_on_position = abs(arr[i + 1] - arr[i])
                    minimum_element = i
                    side = i + 1


        current_positions[side] = True
        visited[side] = True
        counter += abs(arr[minimum_element] - arr[side])

    return counter

for i,line in enumerate(sys.stdin):
    if i == 0:
        N, M = int(line.split(" "))
    if i == 1:
        A = [int(i) for i in line.split(" ")]
        solution(A, M)

# line = "-10 -3 0 9 -100 2 17"
#

# print("before")
# a = [10,12,1,2,14]
# b = [-100000]
# print(solution(lines, 3))
# print(solution(a, 2))
# print(solution(b, 1))


import math
import sys
from heapq import heappush, heappop


def solution(arr, moves):
    if len(arr) <= moves:
        return 0

    arr.sort()
    if moves == 1:
        return abs(arr[0] - arr[-1])

    heapq_max = []
    # place them then scan the array
    # right side of longest interval

    for i in range(0, len(arr) - 1):
        heappush(heapq_max, (-abs(arr[i] - arr[i + 1] ), i , i + 1))

    placed = [0]
    for _ in range(moves - 1):
        val = heappop(heapq_max)
        placed.append(val[2])

    placed.sort()
    counter = 0
    for i in range(len(placed) - 1):
        if (abs(placed[i] -  placed[i + 1]) > 1):
            counter += abs(arr[placed[i]] - arr[placed[i + 1] - 1])
    if placed[-1] != len(arr) - 1:
        counter += abs(arr[placed[-1]] - arr[-1])
    return counter

    # visited = {}
    # current_positions = {}
    #
    
    #     visited[i[0]] = True
    #     current_positions[i[0]] = True
    #
    # counter = 0
    # while len(visited) < len(arr):
    #     min_on_position = sys.maxsize
    #     minimum_element = None
    #     side = None
    
    #         if i - 1 not in visited and i > 0:
    #             if min_on_position > abs(arr[i - 1] - arr[i]):
    #                 min_on_position = abs(arr[i - 1] - arr[i])
    #                 minimum_element = i
    
    #
    #         if i + 1 not in visited and i < len(arr) - 1:
    #             if min_on_position > abs(arr[i + 1] - arr[i]):
    #                 min_on_position = abs(arr[i + 1] - arr[i])
    #                 minimum_element = i
    
    #
    #
    #     current_positions[side] = True
    #     visited[side] = True
    #     counter += abs(arr[minimum_element] - arr[side])
    #
    # return counter

for i,line in enumerate(sys.stdin):
    if i == 0:
       M, N = line.split(" ")
    if i == 1:
        A = [int(i) for i in line.split(" ")]
        print(solution(A, int(M)))

# line = "-10 -3 0 9 -100 2 17"
#

# a = [10,12,1,2,14]
# b = [-100000]
# print(solution(lines, 3))
# print(solution(a, 2))
# print(solution(b, 1))


Verdicts: Runtime Error

Accepted