Given an array arr[][] consisting of N pairs such that each pair {L, R} represents that ith house can be painted in L number of days before the Rth day, the task is to find the maximum number of house that can be painted continuously.
Examples:
Input: N = 4, paint[ ][ ] = [[1, 19], [2, 2], [4, 17], [1, 1]]
Output: 3
Explanation: Maximum of three houses can be painted and order is {4, 3, 1}Input: N = 4, paint[ ][ ] = [[100, 210], [200, 1310], [1000, 1275], [2500, 3000]]
Output: 3
Approach: The problem can be solved using the greedy approach. The idea is to choose from the lowest DaysRequired within the current LastDay. Follow the steps below for the approach.
- Initialize a vector, say V, to store all the pairs which can be taken.
- Sort the vector V by using a comparator pair.second less than pair.first
- Initialize a priority queue pq and push the first pair of the vector V.
- Initialize a variable, say t, to store the time.
- Traverse the vector, V and put the current pair in priority queue pq:
- If t + DaysRequired is less than or equal to LastDay, then continue.
- else, pop from the priority queue, store in temp variable and also update t equals t – temp.first
- Finally, return the size of the priority queue.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; typedef vector<vector< int > > Matrix; // Comparator for sorting static bool cmp(pair< int , int > a, pair< int , int > b) { return a.second < b.second; } // Function to count number of houses // that can be painted void countMaxPinted( int n, Matrix& paint) { // Vector to store the pairs vector<pair< int , int > > V; for ( int i = 0; i < n; i++) { // If house can be painted if (paint[i][0] <= paint[i][1]) { V.push_back(make_pair(paint[i][0], paint[i][1])); } } // Sort the vector sort(V.begin(), V.end(), cmp); // If vector is empty if (V.size() == 0) { cout << 0 << endl; return ; } // Initialize t int t = V[0].first; // Initialize priority queue priority_queue<pair< int , int > > pq; pq.push(V[0]); // Traversing the vector for ( int i = 1; i < V.size(); i++) { t += V[i].first; // Pushing in Vectors pq.push(V[i]); if (t <= V[i].second) { continue ; } else { // Pop the top element auto temp = pq.top(); pq.pop(); t = t - temp.first; } } // Print the ans cout << pq.size() << endl; } // Driver Code int main() { // Given Input int n = 4; Matrix paint = { { 1, 19 }, { 2, 2 }, { 4, 17 }, { 1, 1 } }; // Function Call countMaxPinted(n, paint); } |
Java
import java.util.*; public class Main { // Pair class static class Pair { int x, y; Pair( int x, int y) { this .x = x; this .y = y; } } // Comparator to sort by second element static class SortBySecond implements Comparator<Pair> { public int compare(Pair a, Pair b) { return a.y - b.y; } } public static void main(String[] args) { // Given Input int n = 4 ; int [][] paint = { { 1 , 19 }, { 2 , 2 }, { 4 , 17 }, { 1 , 1 } }; // Vector to store the pairs ArrayList<Pair> V = new ArrayList<Pair>(); for ( int i = 0 ; i < n; i++) { // If house can be painted if (paint[i][ 0 ] <= paint[i][ 1 ]) { V.add( new Pair(paint[i][ 0 ], paint[i][ 1 ])); } } // Sort the vector V.sort( new SortBySecond()); // If vector is empty if (V.size() == 0 ) { System.out.println( 0 ); return ; } // Initialize t int t = V.get( 0 ).x; // Initialize priority queue PriorityQueue<Pair> pq = new PriorityQueue<>( new SortBySecond()); pq.add(V.get( 0 )); // Traversing the vector for ( int i = 1 ; i < V.size(); i++) { t += V.get(i).x; // Pushing in Vectors pq.add(V.get(i)); if (t <= V.get(i).y) { continue ; } else { // Pop the top element Pair temp = pq.poll(); t = t - temp.x; } } // Print the ans System.out.println(pq.size()); } } |
Python3
# Python3 program for the above approach # Function to count number of houses # that can be painted def countMaxPinted(n, paint): # Vector to store the pairs V = [] for i in range (n): # If house can be painted if (paint[i][ 0 ] < = paint[i][ 1 ]): V.append((paint[i][ 0 ], paint[i][ 1 ])) # Sort the vector V.sort(key = lambda x: x[ 1 ]) # If vector is empty if ( len (V) = = 0 ): print ( 0 ) return # Initialize t t = V[ 0 ][ 0 ] # Initialize priority queue pq = [] pq.append(V[ 0 ]) # Traversing the vector for i in range ( 1 , len (V)): t + = V[i][ 0 ] # Pushing in Vectors pq.append(V[i]) if (t < = V[i][ 1 ]): continue else : # Pop the top element temp = pq.pop() t = t - temp[ 0 ] # Print the ans print ( len (pq)) # Driver Code if __name__ = = "__main__" : # Given Input n = 4 paint = [[ 1 , 19 ], [ 2 , 2 ], [ 4 , 17 ], [ 1 , 1 ]] # Function Call countMaxPinted(n, paint) # // This code is contributed by ishankhandelwals. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class Program { // Define the matrix type public static List<Tuple< int , int > > paint; // Comparator for sorting public static int Compare(Tuple< int , int > a, Tuple< int , int > b) { return a.Item2 - (b.Item2); } // Function to count number of houses // that can be painted public static void countMaxPinted( int n) { // List to store the pairs List<Tuple< int , int > > V = new List<Tuple< int , int > >(); for ( int i = 0; i < n; i++) { // If house can be painted if ((paint[i]).Item1 <= (paint[i]).Item2) { V.Add(paint[i]); } } // Sort the list V.Sort(Compare); // If list is empty if (V.Count == 0) { Console.WriteLine(0); return ; } // Initialize t int t = V[0].Item1; // Initialize priority queue SortedList<Tuple< int , int >, int > pq = new SortedList<Tuple< int , int >, int >(); pq.Add(V[0], 0); // Traversing the list for ( int i = 1; i < V.Count; i++) { t += V[i].Item1; // Adding in List pq.Add(V[i], i); if (t <= V[i].Item2) { continue ; } else { // Pop the first element var temp = pq.Keys[0]; pq.RemoveAt(0); t = t - temp.Item1; } } // Print the ans Console.WriteLine(pq.Count); } // Driver Code static void Main( string [] args) { // Given Input int n = 4; paint = new List<Tuple< int , int > >{ Tuple.Create(1, 19), Tuple.Create(2, 2), Tuple.Create(4, 17), Tuple.Create(1, 1) }; // Function Call countMaxPinted(n); } } |
Javascript
// JavaScript conversion of the above Python code // Function to count number of houses that can be painted function countMaxPinted(n, paint) { // Array to store the pairs let V = []; for (let i = 0; i < n; i++) { // If house can be painted if (paint[i][0] <= paint[i][1]) { V.push([paint[i][0], paint[i][1]]); } } // Sort the array V.sort((a, b) => a[1] - b[1]); // If array is empty if (V.length === 0) { console.log(0); return ; } // Initialize t let t = V[0][0]; // Initialize an array as a priority queue let pq = []; pq.push(V[0]); // Traverse the array for (let i = 1; i < V.length; i++) { t += V[i][0]; // Push elements into the array pq.push(V[i]); if (t <= V[i][1]) { continue ; } else { // Pop the first element let temp = pq.shift(); t = t - temp[0]; } } // Log the answer console.log(pq.length); } // Driver Code ( function () { // Given Input let n = 4; let paint = [ [1, 19], [2, 2], [4, 17], [1, 1] ]; // Function Call countMaxPinted(n, paint); })(); // This code is contributed by phasing17. |
3
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!