Costo mínimo para cubrir las posiciones dadas en una grilla N*M

Dada una cuadrícula de n*m ​​y la posición de algunos postes a pintar en la cuadrícula, la tarea es encontrar el costo mínimo para pintar todos los postes. No hay ningún costo involucrado en moverse de una fila a la otra, mientras que moverse a una columna adyacente tiene un costo de 1 rupia asociado. 

Ejemplos:  

Input: n = 2, m = 2, noOfPos = 2
pos[0] = 0, 0
pos[1] = 0, 1

Output: 1
The grid is of 2*2 size and there are two poles at {0, 0} and {0, 1}. 
So we will start at {0, 0} and paint the pole and then go to
the next column to paint the pole at {0, 1} position which will
cost 1 rupee to move one column. 

Input: n = 2, m = 2, noOfPos = 2
pos[0] = {0, 0}
pos[1] = {1, 0}
Output: 0
Both poles are in the same column. So, no need to move to another column. 

Planteamiento: Como existe el único costo de moverse en columnas, si vamos a cualquier columna pintaremos todos los postes en esa columna y luego avanzaremos. Entonces, básicamente, la respuesta será la diferencia entre las dos columnas más lejanas.
A continuación se muestra la implementación requerida: 

// C++ implementation of the above approach
 
#include <iostream>
#include <list>
 
using namespace std;
 
    // Function to find the cost to paint all poles
    void find(int n,int m,int p,int q[2][2])
    {
        // To store all the columns,create list
        list <int> z ;
        int i ;
         
        for(i = 0;i < p;i++)
            z.push_back(q[i][1]);
         
        // sort in ascending order
        z.sort();
         
        // z.back() gives max value
        // z.front() gives min value
        cout << z.back() - z.front() <<endl ;
    }
     
    // Driver code
    int main()
    {
        int n = 2;
        int m = 2;
        int p = 2;
         
        int q[2][2] = {{0,0},{0,1}} ;
         
        find(n, m, p, q);
        
       return 0;
        
    // This code is contributed by ANKITRAI1
    }

// Java implementation of the above approach
 
import java.util.*;
class solution
{
 
    // Function to find the cost to paint all poles
    static void find(int n,int m,int p,int q[][])
    {
        // To store all the columns,create list
        Vector <Integer> z= new Vector<Integer>() ;
        int i ;
         
        for(i = 0;i < p;i++)
            z.add(q[i][1]);
         
        // sort in ascending order
        Collections.sort(z);
         
        // z.back() gives max value
        // z.front() gives min value
        System.out.print(z.get(z.size()-1) - z.get(0) ) ;
    }
     
    // Driver code
    public static void main(String args[])
    {
        int n = 2;
        int m = 2;
        int p = 2;
         
        int q[][] = {{0,0},{0,1}} ;
         
        find(n, m, p, q);
         
          
    }
 
 
 
}
//contributed by Arnab Kundu

# Function to find the cost to paint all poles
import math as ma
 
def find(n, m, p, q):
 
    # To store all the columns
    z =[]
    for i in range(p):
        z.append(q[i][1])
 
    print(max(z)-min(z))
     
n, m, p = 2, 2, 2
q =[(0, 0), (0, 1)]
find(n, m, p, q)

// C# implementation of the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to find the cost to paint all poles
    static void find(int n, int m, int p, int [,]q)
    {
        // To store all the columns,create list
        List <int> z = new List<int>();
        int i;
         
        for(i = 0; i < p; i++)
            z.Add(q[i, 1]);
         
        // sort in ascending order
        z.Sort();
         
        // z.back() gives max value
        // z.front() gives min value
        Console.Write(z[z.Count-1] - z[0]);
    }
     
    // Driver code
    public static void Main(String []args)
    {
        int n = 2;
        int m = 2;
        int p = 2;
         
        int [,]q = {{0, 0}, {0, 1}};
         
        find(n, m, p, q);
    }
}
 
// This code is contributed by PrinciRaj1992

<?php
// PHP implementation of the above approach
 
// Function to find the cost to
// paint all poles
function find($n, $m, $p, $q)
{
    // To store all the columns,
    // create an array
    $z = array();
     
    for($i = 0; $i < $p; $i++)
        array_push($z, $q[$i][1]);
     
    // sort in ascending order
    sort($z);
 
    echo max($z) - min($z);
}
 
// Driver code
$n = 2;
$m = 2;
$p = 2;
 
$q = array(array(0, 0),
            array(0, 1));
 
find($n, $m, $p, $q);
 
// This code is contributed by ita_c
?>

<script>
 
// Javascript implementation of the above approach
// Function to find the cost to paint all poles
function find(n,m,p,q)
{
    // To store all the columns,create list
    var z = [];
    var i ;
     
    for(i = 0;i < p;i++)
        z.push(q[i][1]);
     
    // sort in ascending order
    z.sort();
     
    // z.back() gives max value
    // z.front() gives min value
    document.write( z[z.length-1] - z[0]);
}
 
// Driver code
var n = 2;
var m = 2;
var p = 2;
 
var q = [[0,0],[0,1]];
 
find(n, m, p, q);
 
 
</script>

1

Complejidad de tiempo: O (plogp)

Espacio Auxiliar: O(p)