هر بادکنک که در مسئله داده شده است را راس یک گراف در نظر بگیرید.
بین دو راس یال رسم می کنیم اگر و فقط اگر بتوان با پرتاب یک تیر هر دو بادکنک را زد.
لم: اگر n بازه متناهی داشته باشیم که هر دو تایی باهم اشتراک داشته باشند. نقطه ای وجود دارد که همه ی بازه ها آن را دارند.
ادعا می کنم تنها زمانی می توان با یک تیر m بادکنک را زد که زیر گراف القایی این m بادکنک در گراف خوشه (گراف کامل) باشد.
طرف اول حکم : اگر بتوان m بادکنک را با یک تیر زد حتماً زیر گراف القایی این m راس خوشه است. چون هر دو بادکنک از این m بادکنک را در نظر بگیریم. با توجه به نحوه ی رسم یال ها این تیر باعث می شود که این دو به هم وصل شوند پس در زیر گراف القایی این m بادکنک هر دوتایی به هم وصل شدهاند، پس خوشه است.
طرف دوم حکم: اگر در گراف خوشه m تایی وجود داشته باشد. می توان تیری زد که همه ی این m بادکنک بترکند. برای هر کدام از این m بادکنک بازه ای در نظر بگیرید که نشان دهنده ی زاویه هایی است که اگر تیر در آن زاویه های باشد آن بادکنک می ترکد. حال می دانیم اگر دو بادکنک با یک تیر زده شوند. بازه های آن ها با هم اشتراک دارد. چون زیر گراف القایی این m بادکنک خوشه است یعنی در این m بازه هر دوتایی با هم اشتراک دارد. پس طبق لم زاویه ای هست که همه ی آن ها دارند. پس با پرتاب تیر در آن زاویه همه ی بادکنک ها می ترکند.
حال مسئله ساده شد. چون به اندازه ی تعداد خوشه های ماکسیمال گراف حداقل باید تیر پرتاب کنیم.
نکته: توجه کنبد مهم است که دایره ها بالای محور x ها باشد چون در غیر این صورت ممکن است بازه ها متناهی نشود.
برای دوستان اهل کد زدن جالب است که پیچیدگی این الگوریتم از اردر n*e است!