fork download
copy 
  1. import sys
  2. import time
  3. from itertools import combinations
  4.  
  5. def get_requests(f=sys.stdin):
  6.     """Read requests from stdin according to problem statement"""
  7.     num_requests = int(f.readline())
  8.     starts = f.readline().split()
  9.     ends = f.readline().split()
  10.     return sorted(zip(map(int, starts), map(int, ends)))
  11.  
  12. def requests_overlap(a, b):
  13.     """Check to see if two requests overlap"""
  14.     a, b = sorted((a, b))
  15.     return a[1] >= b[0]
  16.  
  17. def is_valid(requests):
  18.     """Check the validity of a sequence of requests by checking for overlaps"""
  19.     for a, b in combinations(requests, 2):
  20.         if requests_overlap(a, b):
  21.             return False
  22.     return True
  23.  
  24. def int2bit_mask(num, min_length=0):
  25.     """Get the binary representation of a number"""
  26.     mask = []
  27.     while num:
  28.         mask.insert(0, bool(num % 2))
  29.         num //= 2
  30.     while len(mask) < min_length:
  31.         mask.insert(0, False)
  32.     return mask
  33.  
  34. def masks(pop, max_pop):
  35.     """Get all bit masks with a specific population"""
  36.     for bits in combinations(range(max_pop), pop):
  37.         yield [True if bit in bits else False for bit in range(max_pop)]
  38.  
  39. def apply_mask(requests, mask):
  40.     """Get the list of requests represented by a bit mask"""
  41.     return [r for r,b in zip(requests, mask) if b]
  42.  
  43. def brute_force(requests):
  44.     """Method #1"""
  45.     best_count, best = 0, tuple()
  46.     for i in range(2**len(requests)):
  47.         masked = apply_mask(requests, int2bit_mask(i, len(requests)))
  48.         if len(masked) > best_count and is_valid(masked):
  49.             best_count, best = len(masked), masked
  50.     return best_count, best
  51.  
  52. def smarter(requests):
  53.     for pop in range(len(requests), 0, -1):
  54.         for mask in masks(pop, len(requests)):
  55.             masked = apply_mask(requests, mask)
  56.             if is_valid(masked):
  57.                 return pop, masked
  58.  
  59. if __name__ == '__main__':
  60.     requests = get_requests()
  61.  
  62.     start = time.time()
  63.     print('Brute force:', brute_force(requests))
  64.     end = time.time()
  65.     print('Solved in:', end-start)
  66.  
  67.     start = time.time()
  68.     print('Ordered masks:', smarter(requests))
  69.     end = time.time()
  70.     print('Solved in:', end-start)
Success #stdin #stdout 0.02s 28384KB
comments ()
stdin
copy 
10
1 3 5 7 9 11 13 15 17 19
2 4 6 8 10 12 14 16 18 20
stdout
copy 
Brute force: (10, [(1, 2), (3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16), (17, 18), (19, 20)])
Solved in: 0.0040128231048583984
Ordered masks: (10, [(1, 2), (3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16), (17, 18), (19, 20)])
Solved in: 3.3855438232421875e-05
https://ideone.com/zl8Zfi
language:
Python 3 (python  3.12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!