Priyanka and Toys - Greedy

Problem Statement

Little Priyanka visited a kids' shop. There are N toys and their weight is represented by an array W=[w1,w2,…,wN]. Each toy costs 1 unit, and if she buys a toy with weight w′, then she can get all other toys whose weight lies between [w′,w′+4] (both inclusive) free of cost.

Input Format

The first line contains an integer N i.e. number of toys.
Next line will contain N integers, w1,w2,…,wN, representing the weight array.

Output Format

Minimum units with which Priyanka could buy all of toys.

Constraints 
1≤N≤105
0≤wi≤104,where i∈[1,N]

Sample Input

5
1 2 3 17 10

Sample Output

3

Explanation

She buys 1st toy with weight 1 for 1 unit and gets 2nd and 3rd toy for free since their weight lies between [1,5]. And she has to buy last two toys separately.

Copyright © 2015 HackerRank.
All Rights Reserved

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) throws IOException{
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String s = br.readLine();
        String[] tmp = s.split(" ");
        int[] weight = new int[n];
        for(int i = 0 ; i < n ; i++)
            {
            weight[i] = Integer.parseInt(tmp[i]);
        }
        Arrays.sort(weight);
        int x = weight[0], count = 1 ;
        for(int i = 1 ; i < n ; i++)
            {
            if(weight[i] > x + 4)
                {
                count ++;
                x = weight[i];
            }
        }
        System.out.println(count);
    }
}