My issue
I just submitted the answer for this problem. My approach was right but the solution failed in one testcase.
I tried to make my answer as similar to the one given in the solution to find what was wrong in my code, but I still failed at that one testcase and debugger doesn’t display that testcase.
I identified the problem but don’t quite understand it. Turns out while sorting the array I used a custom function which return a.first <= b.first (giving wrong answer to that testcase).
What it should have done is a.first < b.first (without equality).
I fail to see why that matters at all in the above question.
My code
#include <iostream>
#include <bitset>
#include <cmath>
#include <stdio.h>
#include <climits>
#include <stdio.h>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <numeric>
using namespace std;
void testcase();
bool comp(const pair<int,int> &a,const pair<int,int> &b);
int main(){
int t; scanf("%d",&t);
while(t--) testcase();
}
void testcase(){
int n;;
scanf("%d",&n);
vector<pair<int,int>> arr;
for(int i = 0; i < n; i++){
int a, b;
scanf("%d %d", &a, &b);
arr.push_back({a,i});
arr.push_back({b,i});
}
sort(arr.begin(), arr.end(), comp);
int ans = INT_MAX;
vector<bool> check(2*n, false);
int i;
int temp = 0;
if (i<0) i = 0;
for( i= 0; i<2*n; i++){
temp += 1 - check[arr[i].second];
check[arr[i].second] = true;
if (temp != n) continue;
if ((i-1) >= 0){
if (arr[i].second != arr[i-1].second){
ans = min(ans,arr[i].first - arr[i-1].first);
}
else{
if ((i-2) >= 0){
ans = min(ans,arr[i].first - arr[i-2].first);
}
}
}
}
printf("%d\n", ans);
}
bool comp(const pair<int,int> &a, const pair<int,int> &b){
return (a.first <= b.first);
}
Problem Link: SPLITMIN Problem - CodeChef