Last Updated on June 17, 2022 by Ria Pathak
Concepts Used
Sorting
Difficulty Level
Medium
Problem Statement (Simplified):
Print the Strings according to their priority and category. If string belongs to hometown, it will have a priority higher than other towns irrespective of their priority value. String belonging to the same category is printed according to its priority value. More the priority value more will be their priority. Priority values are distinct.
Test Case
Input:
1
3
News1 1 1
News2 2 0
News3 4 1
Output:
News3
News1
News2
Explanation:
News3 and News1 are originated in the hometown so they will be printed first and News3 is more popular than News1 and then News2 will be printed.See original problem statement here
Solving Approach :
1) As we know, if D is 1, i.e. new belongs to hometown they’ll have the highest priority.
2) So we’ll print news from hometown first then news from other towns.
3) News will be printed, in their priority order, news with priority value more will be printed first.
4) As we know all priority values are distinct, so we can save the index of news strings associated with priority value in a separate Index Array.
5) We learn programming languages online and create two separate two arrays to save priority values from hometown news and other towns.
6) When we read news from every line, we save the priority value in its respective array, depending on the value provided in D, where if D is 1, the news is from home town, else news is from another town.
7) We can sort news priority wise by sorting the arrays containing priorities of both towns, hence the news with the highest priority will be on the last index, and news with the least priority will be on the first index.
8) Hence we print news according to priority. We print news from hometown first and then from rest towns.
Example
Solutions
#include <stdio.h>
void merge(int arr[], int start, int mid, int end){
int left[mid-start+1];
int right[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
int main()
{
int test;
scanf("%d", &test);
while(test--){
int n;
scanf("%d", &n);
char news[n][99999];
int popularityAway[99999];
int popularityHome[99999];
int indexing[999999] = {0};
int home=0, away=0, temp;
for(int i=0; i<n; i++){
int val;
scanf("%s%d%d", news[i],&temp,&val);
if(val==1)
popularityHome[home++] = temp;
else
popularityAway[away++] = temp;
indexing[temp] = i;
}
if(away>0)
mergeSort(popularityAway, 0, away-1);
if(home>0)
mergeSort(popularityHome, 0, home-1);
if(home>0){
for(int i=home-1 ;i>=0; i--)
printf("%s\n",news[indexing[popularityHome[i]]]);
}
if(away>0){
for(int i=away-1; i>=0; i--)
printf("%s\n",news[indexing[popularityAway[i]]]);
}
}
}
#include <bits/stdc++.h>
using namespace std;
void merge(int arr[], int start, int mid, int end){
int left[mid-start+1]={0};
int right[end-mid]={0};
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
int main()
{
int test;
cin>>test;
while(test--){
int n;
cin>>n;
char news[n][99999];
int popularityAway[99999];
int popularityHome[99999];
int indexing[999999] = {0};
int home=0, away=0, temp;
for(int i=0; i<n; i++){
int val;
cin>>news[i]>>temp>>val;
if(val==1)
popularityHome[home++] = temp;
else
popularityAway[away++] = temp;
indexing[temp] = i;
}
if(away>0)
mergeSort(popularityAway, 0, away-1);
if(home>0)
mergeSort(popularityHome, 0, home-1);
if(home>0){
for(int i=home-1 ;i>=0; i--)
cout<<news[indexing[popularityHome[i]]]<<endl;
}
if(away>0){
for(int i=away-1; i>=0; i--)
cout<<news[indexing[popularityAway[i]]]<<endl;
}
}
}
import java.util.*;
import java.io.*;
public class Main {
static void merge(int arr[], int start, int mid, int end){
int left[] = new int[mid-start+1];
int right[] = new int[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] = arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}
while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}
while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}
}
static void mergeSort(int arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int test = sc.nextInt();
while(test--!=0){
int n = sc.nextInt();
String news[] = new String[n];
int popularityAway[] = new int[99999];
int popularityHome[] = new int[99999];
int indexing[] = new int[999999];
int home=0, away=0;
for(int i=0; i<n; i++){
news[i] = sc.next();
int temp = sc.nextInt(),val = sc.nextInt();
if(val==1)
popularityHome[home++] = temp;
else
popularityAway[away++] = temp;
indexing[temp] = i;
}
if(away>0)
mergeSort(popularityAway, 0, away-1);
if(home>0)
mergeSort(popularityHome, 0, home-1);
if(home>0){
for(int i=home-1 ;i>=0; i--)
System.out.println(news[indexing[popularityHome[i]]]);
}
if(away>0){
for(int i=away-1; i>=0; i--)
System.out.println(news[indexing[popularityAway[i]]]);
}
}
}
}
def merge(arr, start, mid, end): left = [0 for i in range(mid - start + 1)] right = [0 for i in range(end - mid)] for i in range(start, mid + 1): left[i - start] = arr[i] for i in range(mid + 1, end + 1): right[i - (mid + 1)] = arr[i] leftIndex = 0 rightIndex = 0 arrIndex = start while leftIndex <= mid - start and rightIndex < end - mid: if(left[leftIndex] < right[rightIndex]): arr[arrIndex] = left[leftIndex] leftIndex += 1 else: arr[arrIndex] = right[rightIndex] rightIndex += 1 arrIndex += 1 while(leftIndex <= mid - start): arr[arrIndex] = left[leftIndex] leftIndex += 1 arrIndex += 1 while(rightIndex < end - mid): arr[arrIndex] = right[rightIndex] rightIndex += 1 arrIndex += 1 def mergeSort(arr, start, end): if(end == start): return mergeSort(arr, start, (start + end) // 2) mergeSort(arr, ((start + end) // 2) + 1, end) merge(arr, start, (start + end) // 2, end) for _ in range(int(input())): n = int(input()) indexing = [0] * 999999 news = [] popularityAway = [0] * 99999 popularityHome = [0] * 99999 home, away = 0, 0 for i in range(n): z, temp, val = input().split() temp, val = int(temp), int(val) news.append(z) if val == 1: popularityHome[home] = temp home += 1 else: popularityAway[away] = temp away += 1 indexing[temp] = i if away: mergeSort(popularityAway, 0, away - 1) if home: mergeSort(popularityHome, 0, home - 1) if home: for i in range(home - 1, -1, -1): print(news[indexing[popularityHome[i]]]) if away: for i in range(away - 1, -1, -1): print(news[indexing[popularityAway[i]]])
[forminator_quiz id=”1322″]
Space Complexity
O(
max(n)) space is taken to store indexes.
This article tried to discuss Sorting. Hope this blog helps you understand and solve the problem. To practice more problems on Sorting you can check out MYCODE | Competitive Programming.